现在，确定性素数判定法已经有很多种，常用的有试除法、威廉斯方法、艾德利曼和鲁梅利法。它们的适用范围各不相同，威廉斯方法比较适合10^20 到10^50之间的数，艾德利曼和鲁梅利法适合大于10^50的数，对于32位机器数，由于都小于10^10，所以一般都用试除法来判定。

Miller-Rabin测试现在已经算是过时了。这是一个概率性算法，它只能说一个数很大概率上是素数。不过这在实际应用中已经够了，再加上一直以来没有发现更好的算法，所以它才被广泛使用。人们一直确信素性判定是一个P问题，不过奇怪的是一直没有证明。

大约2002年的时候，也就是Miller-Rabin方法提出的10多年后，三个印度人终于提出了复杂度为P的确定性的素性测试算法。这个算法，也就是所谓的AKS算法，可以在多项式时间里确定的判断一个数是否是素数。目前几乎所有的新软件里面应该都使用了这个算法来做素性测试了，比如java。现在还去研究Miller-Rabin测试，实际的意义已经不大。

AKS算法正式发布版是：Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P." Annals of Mathematics 160(2): 781-793 (2004)
它的2002年最初版和最新修改版都可以在第一作者的主页上下载：http://www.cse.iitk.ac.in/users/mani...lications.html

以下是引用godgoodli在2009-9-17 19:53的发言：

for(k=3;k<=1000;k++)
for(i=2;i<=k/2;i++)
{if(k%i==0)
break;......}
判断1000内的素数。   等号要不要结果都是一样，只是计算机内部认为有差异而已，事实都是对的。  我只是想说明机试计算机的评分方法有问题~无其 ...

以下是引用Devil_W在2009-9-17 11:03的发言：

混乱是因为你看不懂。
 
只要看这个数是6n+1还是6n+5
 
6n+2 6n+3 6n+4 6n的不是素数
 
而这6个的集合可以组成自然数集。
 
低效就不知道怎么看出来的。
 
麻烦你写个。
 
我之前在分析大数的素性判断。
 
一 ...