首先，感谢您分享您的程序并致力于正确性。我认为进行测试很重要，并且在大小边界附近进行筛选是我花时间编写代码的事情。
“到处都是同样的结果：nada、zilch、niente。” 你看的不够仔细。有很多工具可以做到这一点。太糟糕了，primesieve 没有一直达到 2^64-1，但这并不意味着没有其他方法。
“那么，如何才能验证接近 2^64 的筛子的正确操作呢？” 我做的一件事是进行边缘案例测试，该测试贯穿 2^64-1 附近的所有起点/终点组合，验证许多方法都产生相同的结果。这依赖于有一个这些素数的列表来开始，但是有很多方法可以得到这些。这不仅在这个范围内测试筛子，而且测试开始/结束条件以确保那里没有问题。
生成低于 2^64 的一百万个素数的一些方法：
time perl -Mntheory=:all -E 'forprimes { say } ~0-44347170,~0' | md5sum
需要约 2 秒来生成 1M 个素数。我们可以强制使用不同的代码（Perl 或 GMP），使用素数测试等。有很多方法可以做到这一点，is_provable_prime($n)例如，包括循环和调用。还有其他 Perl 模块，包括 Math::Primality，尽管它们要慢得多。
echo 'forprime(i=2^64-44347170,2^64-1,print(i))' | time gp -f -q | md5sum
需要大约 13 秒来生成 1M 个素数。与 Perl 模块一样，有许多替代方法，包括循环调用 isprime，这是一个确定性例程（假设 Pari/GP 的非古代版本）。
#include <stdio.h>
#include <gmp.h>
int main(void) {
mpz_t n;
mpz_init_set_str(n,"18446744073665204445",10);
mpz_nextprime(n, n);
while (mpz_sizeinbase(n,2) < 65) {
/* If you don't trust mpz_nextprime, one could add this:
* if (!mpz_probab_prime_p(n, 100))
* { fprintf(stderr, "Bad nextprime!\n"); return -1; }
*/
gmp_printf("%Zd\n",n);
mpz_nextprime(n, n);
}
mpz_clear(n);
return 0;
}
大约需要 30 秒并获得相同的结果。这个更令人怀疑，因为我不像 BPSW 或其中一种证明方法那样信任它的 25 个预设随机基础 MR 测试，但在这种情况下并不重要，因为我们看到结果匹配。添加额外的 100 个测试在时间上非常昂贵，但极不可能产生错误结果（我怀疑我们有重叠的碱基，所以这也很浪费）。
from sympy import nextprime
n = 2**64-44347170;
n = nextprime(n)
while n < 2**64:
print n
n = nextprime(n)
使用 Python 的 SymPy。不幸的是，当给定 2^64-1 时，primerange 会使用疯狂的内存，因此无法使用。执行简单的 nextprime 方法并不理想——大约需要 5 分钟，但会产生相同的结果（当前 SymPy isprime 使用 46 个素数基数，这比 2^64 下的确定性结果所需的要多得多）。
还有其他工具，例如 FLINT、GAP 等。
我意识到，由于您使用的是 Windows，因此世界很不稳定，很多事情都无法正常工作。我已经在 Windows 上测试了 Perl 的 ntheory，并且在命令提示符下使用 Cygwin 和 Strawberry Perl 我得到了相同的结果。假设 GMP 正常工作，则 GMP 代码应该可以正常工作。
编辑添加：如果您的结果与其中一种比较方法不匹配，则两种（或两者）之一是错误的。可能是比较代码错了！如果您发现并报告错误，它可以帮助每个人。这不太可能，但可能它们都以同样的方式出错，这就是为什么我喜欢与尽可能多的其他来源进行比较。对我来说，这比选择一个“黄金”代码进行比较更强大。尤其是如果您使用可能尚未经过彻底测试的古怪平台。
对于 BPSW，有一些实现：
- 帕里。AES Lucas，在 Pari 源代码中，所以不确定它的可移植性。
- TR 很好。强大的 Lucas，独立代码。
- 大卫克利弗。标准、强或特强卢卡斯。独立库，非常清晰，非常好用。
- 我的非 GMP 代码，包括 x86_64 的 asm Montgomery 数学。当然比 bigint 代码快很多。
- 我的 GMP 代码。标准、强、AES 或超强 Lucas。比其他 bigint 代码更快。还有其他 Frobenius 和其他复合性测试。可以独立制作。
- 我有一个使用 LibTomMath 的版本，我希望能进入其中一个 Perl6 VM。仅当您想使用 LTM 时才有趣。
所有验证与 Feitsma 数据。我敢肯定还有更多的实现。FLINT 有一个非常快的变体，但它并不是真正的 BPSW（但它已针对 2^64 以下的数字进行了验证）。