C++几种常见的素数判断算法

求解一个算法,我们首先要知道它的数学含义.依据这个原则,首先我们要知道什么是素数.; 

素数是这样的整数,它除了表示为它自己和 1 的乘积以外,无论他表示为任何两个整数的

乘积。 

找素数的方法多种多样。
1：是从 2

“

”

开始用 是则留下，不是则去掉 的方法把所有的数列出来（一直列到你不想

再往下列为止，比方说，一直列到 10，000）。第一个数是 2，它是一个素数，所以应

当把它留下来，然后继续往下数，每隔一个数删去一个数，这样就能把所有能被 2 整除、

因而不是素数的数都去掉。在留下的最小的数当中，排在 2 后面的是 3，这是第二个素

数，因此应该把它留下，然后从它开始往后数，每隔两个数删去一个，这样就能把所有
能被 3 整除的数全都去掉。下一个未去掉的数是 5，然后往后每隔 4 个数删去一个，以

除去所有能被 5 整除的数。再下一个数是 7，往后每隔 6 个数删去一个;再下一个数是
11，往后每隔 10 个数删一个;再下一个是 13，往后每隔 12 个数删一个。就这样依法做

下去。
但是编程我们一般不采用上面的方法，并不说这中方法计算机实现不了，或者说实现算

法比较复杂。因为它更像一个数学推理。最后我们也给一个算法。
下面我们介绍几种长用的编程方法。
2：遍历 2 以上 N 的平方根以下的每一个整数，是不是能整除 N;(这是最基本的方法）
3：遍历 2 以上 N 的平方根以下的每一个素数，是不是能整除 N;(这个方法是上面方法的

改 进 ， 但 要 求 N 平 方 根 以 下 的 素 数 已 全 部 知 道 )  
4：采用 Rabin-Miller 算法进行验算;

例如：N=2^127-1 是一个 38 位数，要验证它是否为素数，用上面几个不同的方法：

验 算 结 果 ， 假 设 计 算 机 能 每 秒 钟 计 算 1

 

亿 次 除 法 ， 那 么

算法 2 要用 4136 年，算法 3 要用 93 年，算法 4 只要不到 1 秒钟！(这些数据是通过计

算得到)

另外印度有人宣称素数测试是 P 问题，我一直没有找到那篇论文，听说里面有很多数学

理论。如果那位大人有这篇论文，麻烦转发一份。

下面我们分别实现上面的三种算法：
以下算法我们不涉及内存溢出，以及大数字的问题。如果测试数字超过 2^32，发生内

存溢出，你需要自己使用策略解决这个问题，在这里只讨论 32 位机有效数字算法。
1  

： 算法 0：是从 2

“

”

开始用 是则留下，不是则去掉 的方法把所有的数列出来

最后数组中不为 0 的数字就是要查找的素数。
void PrimeNumber0()

{
int time GetTickCount();

cout start time time endl;
 

int Max[MAX_NUMBER]; 在栈上分配，栈上空间要求一般都在 2M 之间，

如果你需要更大空间，请在堆上申请空间(就是通过 malloc，new 来申请).

memset(Max,0,MAX_NUMBER);
for(int i = 0 ; i MAX_NUMBER; ++i)

{
Max[i] = i;

}
int cout = 0; 记录当前 i 的位置

 

遍历整个数组
for(i = 1; i MAX_NUMBER; ++i)
{

if(Max[i] != 0 ) 如果数据不为 0，说明是一个素数
{

int iCout = i;
int j = Max[i]; 记录数组中数组位的数字，以便设置

while((iCout+=j) MAX_NUMBER)
{