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