DJ Bernstein的'primegen'计划中10 ^ 15的限制来自哪里？

Question

在http://cr.yp.to/primegen.html,您可以找到使用Atkin筛子生成素数的程序源.正如作者所说,回复发送给他的电子邮件可能需要几个月的时间(我明白,他肯定是一个被占领的人!)我发布了这个问题.

该页面指出'primegen可以生成高达1000000000000000的质数'.我试图理解为什么会这样.当然有一个限制,最多2 ^ 64~2*10 ^ 19(长无符号整数的大小),因为这是数字的表示方式.我肯定知道,如果存在巨大的空隙(> 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 作为下限开始，您会取得不同的成功。