c - 埃拉托色尼筛法求素数的进一步加速

Question

我看到了这个使用 Eratosthenes 的 Sieve 方法查找素数的 c 代码，但由于分配如此大的 char 数组的内存消耗，我无法将其扩展到更大的整数（例如，1000000000 甚至更大）。

将代码扩展到更大数字的策略是什么？也欢迎任何参考。

谢谢。

Answer 1

应用的标准改进是将每个i-th 位视为表示数​​字2*i+1，因此仅表示赔率，将数组的大小减半。对于每个新的素数，这还需要p从 开始标记p*p并递增2*p，以跳过偶数。2本身就是一个特例。另见这个问题有很多答案。

另一种策略是改用分段筛。这样，您只需要为初始素数序列预留pi(sqrt(m)) = 2*sqrt(m)/log(m)内存（作为您的上限），您可以使用这些素数筛选较小的固定大小的数组，顺序表示数字段。m如果您只需要某个狭窄的遥远范围[m-d,m]内的素数，则在收集完所有需要的素数后，您将直接跳到筛选该范围，如this answer所示。

根据您的具体情况，要获得高达 10^9 的素数，仍然可以使用一个连续的数组。仅将位数组用于赔率，您需要 10^9/16 字节，即大约 60 MB 的内存。更容易分段工作；我们只需要 31627 以下的 3402 个素数来筛选 10^9 以下的每个段数组。

Answer 2

正是由于所需阵列的大小，埃拉托色尼筛法在某些时候变得不切实际。修改后的筛子通常可以找到更大的素数（如Wikipedia 中所述）。

Answer 3

你可以使用gmp图书馆。请参阅加速 Python 中的位串/位操作？用于快速实施埃拉托色尼筛法。将提供的解决方案翻译成 C 语言应该相对容易。