10000以内的质数

生成有100000个质数的质数表的一种较快算法

湖大09通信一班郑锦涛

这里所说的“质数表”是指从最小的质数2开始的所有质数构成的数

列。一般用一维整数数组来储存。

在ACM练习、竞赛中，很多题目都用到了质数表，而在平时编程时，生

成质数的代码也被反复使用，因此，掌握一种较为快速的生成质数表的算法是很

有意义的，也是很有必要的（当数据规模很大时，一个优秀的算法所节省的时间

相当可观）。

生成质数表比较通俗的主要有两种算法，一个被称为欧几里得筛法，另

一个就是用试除法：检验每个数是不是质数，是的话就把它塞进质数表里。

欧几里得筛法是这样的：要得到2~n之间的所有质数，写下2~n之间的所

有整数，然后找数列中最小的数，也就是2；把2留下，删掉所有2的倍数；再回

过头来，找到数列中最小的数3，删掉所有3的倍数……如此反复，直到没有数可

删为止。归结起来，就是在2~n的整数中，不断进行以下操作：找出最小的数m，

删除km（k>1，km<=n），最后剩下的就是质数。

试除法更加直观，直接拿一个数来判断它是不是质数：只要依次检验

2~n-1之间是否有能整除n的数就可以了，只要有一个数能整除n，n就不是质数。

但这个办法太笨，用时太多。对于n/2+1~n-1之间的数来说，显然都不可能整除

n，因此只需要用2~n/2来试除就行了。

但这就是最快的吗？非也。实际上，再想一下可以发现。如果n能被m

整除，则n必然也能被n/m整除；也就是说，如果n有一个约数为m，那它必然

也会有一个约数n/m，于是就不需要再用n/m来试除了。当m*m=n时，

m=n/m，所以只需要检验从2~sqrt(n)之间的数即可。由于出现了平方根，

这样需要试除的数就大为减少。

但这仍然不是最快的方法。回忆一下小学时我们如何判

断质数，并不是用2,3,4…依次试除，而只是用一些质数去试除。这样有个问

题就出来了：要判断质数，生成质数表，但为了判断质数，又需要提前知道一些

质数以便来试除。看上去有些矛盾。其实这个问题也非常好解决。

前面说过，判断一个数n是否是质数需要用2~sqrt(n)之间的数去试除；

现在更进一步，只要用2~sqrt(n)之间的所有质数去试除就行了。2~sqrt(n)之间

的质数如果得到呢？从之前质数表里得到。于是，问题就转化成了为了生成更大

的质数表，需要准备一个较小的质数表，然后把判断为是质数的数逐个放进质

数表里去，生成更大的质数表。初始时，质数表里有一些元素。

以下我写了一个小程序，用来生成并输出100000个质数,运行时间会比较长，

那是因为时间都浪费在输出上了，其实计算只需要1秒不到。

代码如下：

#include

#include

#defineN100000//生成100000个质数

usingnamespacestd;

intprime[N];//一个全局数组，用来保存质数表

voidmakeprime()//生成质数表的子函数

{intj,n=29,i=9,sqrtn;//从第10个质数开始计算，第10个质数

是29

prime[0]=2;

prime[1]=3;

prime[2]=5;

prime[3]=7;

prime[4]=11;

prime[5]=13;

prime[6]=17;

prime[7]=19;

prime[8]=23;//之前已有9个质数在表中

while(i

{

j=0;//每次从表头开始试除

sqrtn=sqrt(n);//n的平方根

while(prime[j]<=sqrtn)

{

if(n%prime[j]==0)break;//若n能整除质数表中的某数，

则跳出

j++;

}

if(prime[j]>sqrtn){prime[i]=n;i++;}

n+=2;//除了2，偶数不会是质数，因此跳过所有偶数

}

}

intmain()

{

makeprime();

for(inti=1;i

{cout<

行

system("pau");

return0;}