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

生成有100000个质数的质数表的一种较快算法湖大09通信一班 郑锦涛这里所说的“质数表”是指从最小的质数2开始的所有质数构成的数列。一般用一维整数数组来储存。 在ACM练习、竞赛中，很多题目都用到了质数表，而在平时编程时，生成质数的代码也被反复使用，因此，掌握一种较为快速的生成质数表的算法是很有意义的，也是很有必要的（当数据规模很大时，一个优秀的算法所节省的时间相当可观）。 生成质数表比较通俗的主要有两种算法，一个被称为欧几里得筛法，另一个就是用试除法：检验每个数是不是质数，是的话就把它塞进质数表里。 欧几里得筛法是这样的：要得到2n之间的所有质数，写下2n之间的所有整数，然后找数列中最小的数，也就是2；把2留下，删掉所有2的倍数；再回过头来，找到数列中最小的数3，删掉所有3的倍数如此反复，直到没有数可删为止。归结起来，就是在2n的整数中，不断进行以下操作：找出最小的数m，删除km（k1，km=n），最后剩下的就是质数。 试除法更加直观，直接拿一个数来判断它是不是质数：只要依次检验2n-1之间是否有能整除n的数就可以了，只要有一个数能整除n，n就不是质数。但这个办法太笨，用时太多。对于n/2+1n-1之间的数来说，显然都不可能整除n，因此只需要用2n/2来试除就行了。 但这就是最快的吗？非也。实际上，再想一下可以发现。如果n能被m整除，则n必然也能被n/m整除；也就是说，如果n有一个约数为m，那它必然也会有一个约数n/m，于是就不需要再用n/m来试除了。当m*m=n时，m=n/m，所以只需要检验从2sqrt(n)之间的数即可。由于出现了平方根，这样需要试除的数就大为减少。 但这仍然不是最快的方法。回忆一下小学时我们如何判断质数，并不是用2, 3, 4依次试除，而只是用一些质数去试除。这样有个问题就出来了：要判断质数，生成质数表，但为了判断质数，又需要提前知道一些质数以便来试除。看上去有些矛盾。其实这个问题也非常好解决。 前面说过，判断一个数n是否是质数需要用2sqrt(n)之间的数去试除；现在更进一步，只要用2sqrt(n)之间的所有质数去试除就行了。2sqrt(n)之间的质数如果得到呢？从之前质数表里得到。于是，问题就转化成了为了生成更大的质数表，需要准备一个较小的质数表，然后把判断为是质数的数逐个放进质数表里去，生成更大的质数表。初始时，质数表里有一些元素。以下我写了一个小程序，用来生成并输出100000个质数,运行时间会比较长，那是因为时间都浪费在输出上了，其实计算只需要1秒不到。代码如下：#include#include#define N 100000 /生成100000个质数 using namespace std;int primeN; /一个全局数组，用来保存质数表 void makeprime()/生成质数表的子函数 int j,n=29,i=9,sqrtn;/从第10个质数开始计算，第10个质数是29 prime0=2; prime1=3; prime2=5; prime3=7; prime4=11; prime5=13; prime6=17; prime7=19; prime8=23; /之前已有9个质数在表中 while (iN) /i是计数变量 j=0; /每次从表头开始试除 sqrtn=sqrt(n); /n的平方根 while (primejsqrtn)primei=n; i+; n+=2; /除了2，偶数不会是质数，因此跳过所有偶数 int main() makeprime(); for (int i=1