c - 进一步加速Eratosthenes的Sieve方法寻找素数

Question

我看到了this c code使用 Eratosthenes 的 Sieve 方法查找素数，但我无法将其扩展到更大的整数(例如，扩展到 1000000000 甚至更大)，因为分配这么大的 char 数组会消耗内存。

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

谢谢。

Answer 1

要应用的标准改进是将每个 i 位视为代表数字 2*i+1，从而代表 几率只有，将数组的大小减半。对于每个新素数 p，这还需要从 p*p 开始标记并递增 2*p，以跳过过平局。 2 本身就是一个特例。另见 this question有很多答案。

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

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