这个方法也是一个确定性方法，如下所示:
bool isPrime(int a){
if( a <= 0) return false;
if( a == 1) return false;
if( a == 2) return true;
if( a == 3) return true;
int sqr = sqrt(a)+1;
if( a%2 == 0) return false;
for(int i=3;i<=sqr;i+=2){
if( a%i == 0 )
return false;
}
return true;
}
如果您的输入小于2^64(对于使用int的示例来说已经足够了)，有一些很好的方法:
1) BPSW。快速，确定性，对所有64位输入正确，没有已知的反例(尽管我们相信它们存在)
2)确定性米勒-拉宾。Wikipedia页面给出了一些正确但效率低下的基集——Best Known SPRP Bases中的基集最适合64位输入。对任何64位输入最多进行7次测试。新的(2015年9月)结果给出了具有13个测试的81位输入的确定性结果。
3)哈希确定性M-R。这只是对#2的优化。32位输入只需要一个M-R测试，64位输入只需要2或3个M-R测试。参见Forisek和Jancina 2015年的论文和我不同的散列实现。
试除法，你展示的方法，对于很小的输入，比如小于100万左右，是很好的。在这之后的一段时间内，它在计算上仍然是可以的，但是它是输入比特长度的指数时间。它的速度非常快，超过26位左右就无法使用了(只是因为巨大的时间增长)。在我的测试中，在25位数时，它比BPSW慢400倍(这种大小的PRP测试)，比ECPP慢1300倍，比APR-CL慢3M倍。
大输入
原数测试的运行时间图如果输入大于64位，一些选项包括:
BLS75方法(来自1975年的开创性论文)，包括N-1, N+1和基于部分分解的混合方法。它们仍然在使用，并且对于高达40位的数字来说速度惊人。广义波克林顿是其中一个定理的特例。由于这依赖于n-1和/或n+1的部分因式分解，因此它通常不能很好地扩展，并且在实际使用中会在80-100位左右失败。
APR-CL。相当快(例如，200位数只需半秒)。在Pari/GP和mpz_aprcl中开源。
ECPP。对于非特殊形式的大输入，最快的方法。Primo(免费使用和黄金标准)，ecpp-dj(开源)。这使用了随机化，所以在某种意义上它不是决定性的，但它是100%正确的，这就是许多人在这种情况下的意思。它还可以提供一个证书，用于快速的第三方验证，这使得它特别有吸引力。
部。可怕地缓慢。理论上的突破和令人着迷的简单数学，但实际上毫无用处。它比20位左右的试除法快，最终将通过BLS75方法，但它远不及我们通常使用的方法:APR-CL或ECPP。有各种各样的实现，我所知道的最快的是ecpp-dj和Perl/ntheory[注意:我是作者]。多项式时间，但指数高于APR-CL的输入低于一千万亿左右的数字(荒谬的大尺寸)。
是的，我认为……确定性算法。另一个更有效的确定性素数测试算法是AKS素数测试。此外，如果你想使用一些概率(非确定性)原数测试，你可以参考米勒-拉宾测试。