使用预先计算的素数筛选Eratosthenes

Question

我已经可以存储所有32位质数，unsigned int并且 我想用它们来生成一些64位质数 。即使对逻辑和编译进行了优化，使用试验划分也太慢了。

我正在尝试修改Eratosthenes的筛网以使用预定义列表，如下所示：

1. 在数组A中从2到4294967291
2. 在数组B中从2 ^ 32到X inc减1
3. 找到C，它是当前素数的第一个倍数。
4. 从C标记开始并以当前素数跳至X。
5. 转到1。

问题是使用模数查找素数的第3步，这种操作是我不使用轨迹除法的原因。

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

谢谢。

Answer 1

增加2，而不是1。这是您应始终使用的最小优化-仅适用于赔率。无需打扰。

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

用分段筛子预先计算您的核心素数。然后继续按适合您缓存的足够大的段进行工作，而无需在核心列表中添加新的素数。对于每个素数，都需要 p 维持long long int value其当前倍数（当然是从素数的平方开始）。步长值是值的 两倍p，或 p 在奇数填充的筛子数组中偏移，其中
i -th项代表number o + 2i ， o 是不低于范围起点的最小奇数。无需按倍数的值排序，核心素数使用的上限单调增加。

sqrt（0xFFFFFFFFFF）=
1048576
。PrimePi（1048576）=
82025
素数是核心素数列表中所需的全部。那是花生。

long long ints的整数算术应该可以很好地找到模数，因此在您首次启动（或恢复工作）时应找到范围的最小倍数。