基于AKS素性检测的素数生成器

1.      解题思路

AKS算法整体包括六个步骤，它本身相当于一个过滤器，只有经过各种条件筛选以后的数才是素数。步骤如图 1所示。

1.  Step1就是判断n是否是一个数的幂次方形式，如果是的话就表明n是合数，程序结束。
2.  Step2需要找出比(log₂n)²大的最小的欧拉函数r。
3.   Step3是找出gcd(a,n)，如果存在a<=r的情况，则输出合数
4.  Step4表明如果n<=r，则输出素数。
5.  Step5是最麻烦的一部，其中涉及到了多项式取模运算，对于多项式的取模运算我们这里使用了一个叫做NTL的C++类库。对一个多项式取模结果进行判断，如果对于某个小范围的a，只要存在多项式，模运算结果不等的情况，则输出宿舍。
6.    Step6表示经过了前面多个step的过滤，依然存在的数就是素数。

程序源代码如下：（用到了NTL类库，使用方法参考前面的几篇博客）

View Code

本文转自xwdreamer博客园博客，原文链接：http://www.cnblogs.com/xwdreamer/archive/2011/03/28/2297035.html，如需转载请自行联系原作者