寻求解素数的C程序

kakuyou

传说下面这个算法是已知计算一个数是否是素数最快的方法，不知道有没有相关的C
语言实现，因为那篇论文我的数学知识看不懂。

http://lijh.bj4hs.edu.cn/newmath/primality.pdf

参考
-----------------------------------------------------------------
日前，印度的三位计算机专家震惊了数学界，他们不但为古老的素数判定问题找到了答案，而且令人始料未及的是，他们的判定方法出奇地简单，简单到足以让数学家们警觉起来，启发他们重新审视许多复杂问题的解决方法。
作为除了1和自身外没有其他约数的正整数，数千年来素数一直是数论的基本构件。对于如何判定一个数是否为素数，公元前240年，希腊数学家埃拉托色尼给出了一个一直沿用到今天的方法——“筛选法”。该方法有其局限性，即随着数字的增大，筛选所耗用的时间呈指数增长。如果要判定相当大的自然数，哪怕采用最先进的计算机进行运算，计算时间比宇宙年龄都要长。因此，长期以来，数学家们一直致力于寻找的，就是在可以接受的时间内能够完成的判定方法。
在过去的几十年间，由于素数判定问题被引入了密码学领域，这方面的研究工作变得倍受关注。因为当前的因特网加密程序，主要是基于大数的素因子分解相当困难这一假定。虽然目前有一些高速程序可以给出一个大数是素数的概率，但它毕竟没有彻底解决问题。
印度理工学院计算机科学与工程学系的科学家马宁德拉·阿格拉瓦和他的两位在校本科生尼拉叶·卡雅尔和尼汀·萨克斯特纳在这方面取得了成功。
这三个人的成功主要得益于采用了崭新的思路。其他人的着眼点往往是“这个数是否是素数”，他们却另辟蹊径，将问题转化成关于待判定数的一系列小的问题或 “方程”。于是，简单的算法诞生了，只需用13行便可写明。阿格拉瓦解释说：“如果某个数字使所有等式成立，那么它就是素数；否则，便不是。”
卡尔·波默朗斯是美国新泽西州贝尔实验室的素数问题专家，他评论说：“这是一个漂亮的算法，我为之高兴。同时，也很遗憾自己没找到它。他们的方法很简洁，但并不平凡。他们的工作充满智慧。”
英国沃里克大学的数学家和科普作家伊恩·斯图亚特认为，这一理论突破就其本身而言固然重要，但它给人们思路上带来的启发意义更加深远。如果采用它所蕴含的换个角度、化繁为简的思想，对于那些目前处在死胡同中的难题，科学家们也许可以找到解决办法。
因特网安全目前还未因此受到威胁。来自英国一个加密安全公司的本·哈德利说：“相对于原来的概率计算算法，新算法并没有给素因子分解提供好的算法，所以这一新突破对密码安全行业并没有太大的实际影响。”
但是，波默朗斯坚信新算法将使密码学专家担忧。他认为，既然存在简单的素数判定算法，也就很可能存在简单的素因子分解算法，只是我们还没注意到罢了。
这恐怕也正是阿格拉瓦等人研究工作的真正意义所在。两名本科生的毕业项目能产生如此重大的成果，这说明我们很可能忽略掉了更多重大数学问题的简单解答方法。波默朗斯感慨颇深地说：“这是一个提醒，原来我们非常容易忽略掉一些简单的东西。”

mozilla

我的数学更不行

Kan

古老点的，一个一个算过去不就结了.算到某个数的1/2为止.

atfa

哪13个公式？