DJ Bernstein 的《primegen》中 10^15 的限制在哪里？程序从何而来？

Question

在 http://cr.yp.to/primegen.html 您可以找到以下程序的来源：使用阿特金筛来生成素数。正如作者所说，可能需要几个月的时间才能回复发送给他的电子邮件（我明白，他确实是一个忙碌的人！）我发布了这个问题。

该页面指出“primegen 可以生成最多 1000000000000000 个素数”。我试图理解为什么会这样。当然，最大限制是 2^64 ~ 2 * 10^19（long unsigned int 的大小），因为这就是数字的表示方式。我确信如果存在巨大的素数间隙（> 2^31），那么数字的打印将会失败。然而，在这个范围内，我认为不存在这样的素数差距。

要么是作者高估了界限（实际上大约是 10^19），要么是源代码中的某个地方算术运算可能会溢出或类似的情况。

有趣的是，你实际上可以运行它来获取数字 > 。 10^15：

./primes 10000000000000000 10000000000000100
10000000000000061
10000000000000069
10000000000000079
10000000000000099

如果您相信 Wolfram Alpha，那么它是正确的。

我进行了“逆向工程”的一些事实：

1. 数字按 1,920 * PRIMEGEN_WORDS = 3,932,160 个数字的批次进行筛选（请参阅 primegen_next.c 中的 primegen_fill 函数）
2. PRIMEGEN_WORDS 控制单次筛选的大小 - 您可以在 primegen_impl.h 中调整它以适应你的CPU缓存，
3. 筛子本身的实现在primegen.c文件中 - 我假设这是正确的；你得到的是 pg->buf 中素数的位掩码（参见 primegen_fill 函数）。
4. 分析位掩码并将素数存储在 pg->p 数组中。

我认为没有任何可能发生溢出的地方。

Answer 1

我希望我能在电脑上查看，但我怀疑如果您从 1 作为下限开始，您会取得不同的成功。

Answer 2

仅从算法来看，我可以得出结论，上限来自 32 位数字。
该页面提到 Pentium-III 作为 CPU，所以我猜它很旧并且不使用 64 位。

2^32 大约是 10^9。阿特金斯筛法（算法使用的）需要 N^(1/2) 位（它使用很大的位域）。这意味着在 2^32 大内存中，您可以（保守）N 约为 10^15。由于这个数字是一个粗略的保守上限（您有系统和其他程序占用内存，为 IO 保留地址范围，...），实际上限可能更高。