使用预先计算的素数筛选埃拉托色尼

Question

我已经可以存储在所有32位质数unsigned int和我想用它来生成一些64位的素数。即使在逻辑和编译方面进行了优化，使用试验除法也太慢了。

我正在尝试修改埃拉托色尼筛以使用预定义列表，如下所示：

1. 在数组 A 中，从 2 到 4294967291
2. 在数组 B 中从 2^32 到 X 加 1
3. 找到 C 是当前素数的第一个倍数。
4. 从 C 标记并通过当前素数跳转到 X。
5. 去 1。

问题是第 3 步使用模数来找到素数倍数，这样的操作是我没有使用跟踪除法的原因。

有没有更好的方法来实现第 3 步或整个算法。

谢谢你。

Answer 1

增加 2，而不是 1。这是您应该始终使用的最小优化 - 仅使用赔率。无需为这些事情而烦恼。

在 C++ 中，vector<bool>用于筛选数组。它会自动位打包。

使用分段筛法预先计算您的核心素数。然后继续按适合您的缓存的足够大的段工作，而无需向核心列表添加新的质数。对于每个素数p保持额外的long long int value：它的当前倍数（当然从素数的平方开始）。步长值是值的两倍p，或p在odds-packed筛数组中的偏移量，其中i-th 条目代表 number o + 2i，o是不低于范围开始的最小奇数。无需按倍数的值排序，核心素数的使用上限单调上升。

sqrt(0xFFFFFFFFFF) = 1048576。PrimePi(1048576)=82025 个素数就是您在核心素数列表中所需要的。那是花生。

long long int当您第一次开始（或继续您的工作）时，s 的整数算术应该可以很好地找到模数，以及范围内的最小倍数。

另请参阅伪代码的相关答案和C 代码的另一个相关答案。