我需要在非常大的数字之间的间隔上测试素数（在 long long 的范围内），所以我需要一些快速算法来检查一个数字是否为素数。请提出你的想法。
问问题
37828 次
10 回答
19
一种好的方法是米勒-拉宾检验。但是应该注意，这只是一个概率测试。
于 2010-04-06T16:47:24.837 回答
18
Jim Sinclair 证明了对七个碱基 2、325、9375、28178、450775、9780504、1795265022 的 Miller-Rabin 测试可以确定性地测试小于 2^64 的数是否为素数。看http://miller-rabin.appspot.com/。
于 2013-08-06T19:16:59.170 回答
10
我相信渐近最快的当前（非概率）素性测试是“Lenstra/Pomerance 改进的 AKS”，它的复杂性基本上是 O(n^6)。
但是，范围long long（假设是 64 位整数的典型系统）并没有那么大。特别是，只有大约 2 亿个小于 2^32 的素数，因此使用快速概率测试，然后使用预先计算的素数列表进行试除（或者只是在素数列表中查找数字，如果你有一个) 在那个范围内会非常快，并且可能是正确的方法。
于 2010-04-06T16:53:45.563 回答
7
我建议使用Miller-Rabin算法的GNU MP 库。我已经用了几个月了，速度非常快。
具体来说，函数 mpz_probab_prime_p 就是这样做的，你也可以使用另一个函数 mpz_nextprime 来查找下一个大于某个数的素数。如果您愿意，我可以发布代码示例。
于 2010-04-06T16:55:59.587 回答
5
如果您想测试 long long 的素数，那么Baillie PSW 素数测试是一个不错的选择。该测试进行了一项强伪素测试和一项卢卡斯测试，因此速度非常快。预计存在一些通过该测试的复合材料，但到目前为止还没有一个已知的，10 15以下当然也不例外。该测试的一个变体例如在 Mathematica 中使用。
于 2010-04-06T21:14:14.737 回答
5
于 2010-04-06T16:46:58.540 回答
1
Cobbal 和 grokus 是对的。Miller-Rabin 检验是可用算法中最有用的。是的，它是概率性的，但真的不应该吓跑你。该测试是最广泛用于实际目的的测试。
请注意，通过重复测试，可以任意减小误报（没有误报）的概率。
于 2010-04-06T17:00:19.867 回答
1
于 2010-04-06T17:03:01.480 回答
-1
我认为最好的算法是“ALI primality test”。
于 2013-08-06T18:36:41.987 回答
-3
最快的可能是在预先计算的素数列表中查找它。例如，请参见此处，它们最多有 2^43112609-1（已知的最大素数）。
于 2010-04-06T16:49:02.983 回答