生成100000个质数的质数表的一种较快算法_湖大09计通院_824 求质数算法

生成有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;}

  

爱华网本文地址 » http://www.413yy.cn/a/25101017/362525.html

更多阅读

让程序窗口化运行的一种简单方法 以窗口模式运行程序

让程序窗口化运行的一种简单方法——简介有些游戏、软件是全屏的,这里介绍让软件窗口化的一种简单方法。让程序窗口化运行的一种简单方法——方法/步骤让程序窗口化运行的一种简单方法 1、找到你要执行的文件,就是你运行时双击的那个

声明:《生成100000个质数的质数表的一种较快算法_湖大09计通院_824 求质数算法》为网友纯真年代分享!如侵犯到您的合法权益请联系我们删除