生成10000以内质数最快方法.doc

生成有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<iostream>
#include<math.h>
#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<N)//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<N;i++)
{cout<<prime[i-1]<<"";if(i%10==0)cout<<endl;}//每输出10个数换行
system("pause");
return0;}