求一种简单的办法快速判定一个正整数为素数

既快速又简单的除了用计算机应该没有了，要不科学家们怎么用了那么多年筛选法呢?看看这个吧

印度的三位计算机专家(one Professor 马宁德拉·阿格拉瓦 + two Bachelors 尼拉叶·卡雅尔和尼汀·萨克斯特纳)震惊了数学界，他们为古老的素数判定问题找到了确定的多项式算法，而且令人始料未及的是，他们的判定方法出奇地简单，简单到足以让数学家们警觉起来，启发他们重新审视许多复杂问题的解决方法。

作为除了1和自身外没有其他约数的正整数，数千年来素数一直是数论的基本构件。对于如何判定一个数是否为素数，公元前240年，希腊数学家埃拉托色尼给出了一个一直沿用到今天的方法——“筛选法”。该方法有其局限性，即随着数字的增大，筛选所耗用的时间呈指数增长。如果要判定相当大的自然数，哪怕采用最先进的计算机进行运算，计算时间比宇宙年龄都要长。因此，长期以来，数学家们一直致力于寻找的，就是在可以接受的时间内能够完成的判定方法。

在过去的几十年间，由于素数判定问题被引入了密码学领域，这方面的研究工作变得倍受关注。因为当前的因特网加密程序，主要是基于大数的素因子分解相当困难这一假定。虽然目前有一些高速程序可以给出一个大数是素数的概率，但它毕竟没有彻底解决问题。

印度理工学院计算机科学与工程学系的科学家马宁德拉·阿格拉瓦和他的两位在校本科生尼拉叶·卡雅尔和尼汀·萨克斯特纳在这方面取得了成功。

这三个人的成功主要得益于采用了崭新的思路。其他人的着眼点往往是“这个数是否是素数”，他们却另辟蹊径，将问题转化成关于待判定数的一系列小的问题或“方程”。于是，简单的算法诞生了，只需用13行便可写明。阿格拉瓦解释说：“如果某个数字使所有等式成立，那么它就是素数；否则，便不是。”

卡尔·波默朗斯是美国新泽西州贝尔实验室的素数问题专家，他评论说：“这是一个漂亮的算法，我为之高兴。同时，也很遗憾自己没找到它。他们的方法很简洁，但并不平凡。他们的工作充满智慧。”

英国沃里克大学的数学家和科普作家伊恩·斯图亚特认为，这一理论突破就其本身而言固然重要，但它给人们思路上带来的启发意义更加深远。如果采用它所蕴含的换个角度、化繁为简的思想，对于那些