我对任意大小的数据类型使用 GMP(带有 MPIR)。我也用了它的素性检验功能，用的是Miller-Rabin方法，但是不准确。这就是我要解决的问题。
我能够通过 sqrt 方法使用蛮力确认数字 18446744073709551253 是素数。
是否有任何方法可以 100% 准确地检查大数是否为素数？
它不应该使用太多的内存/存储空间，几兆字节是可以接受的。
应该比我用的sqrt方法快
它应该适用于大小至少为 64 位或更大的数字。
最后，它应该是 100% 准确的，没有可能!
我有哪些选择？
尽管我可以接受蛮力法(对于 64 位数字)，但出于兴趣，我想要更快更大。此外，64 位数字检查速度太慢:总共 43 秒!
最佳答案
对于非常大的数字，AKS primality test是在时间 O(log7.5n log log n) 中运行的确定性素数测试，其中 n 是感兴趣的数量。这比 O(√n) 算法快得多。但是，该算法具有较大的常数因子，因此在您的数字变得相当大之前它并不实用。
希望这对您有所帮助!
关于c++ - 100% 确定性的快速素数测试？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13829229/