c++ - 使用预先计算的素数的 Eratosthenes 筛法

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 在概率填充筛阵列中的偏移量，其中 i -th 条目代表数字 o + 2i , o 是不低于范围开始的最不奇怪的。无需按倍数排序，核心质数使用上限单调上升。

sqrt(0xFFFFFFFFFF) = 1048576 . PrimePi(1048576)=82025 primes 是您核心素数列表中所需要的全部。那是花生。

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

另请参阅相关的 answer with pseudocode , 和 another with C code .