生成有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>
#define N 100000 //生成100000个质数
using namespace std;
int prime[N]; //一个全局数组,用来保存质数表
void makeprime()//生成质数表的子函数
{int j,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,偶数不会是质数,因此跳过所有偶数
}
}
int main()
{
makeprime();
for (int i=1;i<N;i++)
{cout<<prime[i-1]<<""; if(i%10==0)cout<<endl;}//每输出10个数换行
system("pause");
return 0;}