愛華網(wǎng)生成有100000個質(zhì)數(shù)的質(zhì)數(shù)表的一種較快算法
湖大09通信一班鄭錦濤
這里所說的“質(zhì)數(shù)表”是指從最小的質(zhì)數(shù)2開始的所有質(zhì)數(shù)構(gòu)成的數(shù)列。一般用一維整數(shù)數(shù)組來儲存。
在ACM練習、競賽中，很多題目都用到了質(zhì)數(shù)表，而在平時編程時，生成質(zhì)數(shù)的代碼也被反復使用，因此，掌握一種較為快速的生成質(zhì)數(shù)表的算法是很有意義的，也是很有必要的（當數(shù)據(jù)規(guī)模很大時，一個優(yōu)秀的算法所節(jié)省的時間相當可觀）。
生成質(zhì)數(shù)表比較通俗的主要有兩種算法，一個被稱為歐幾里得篩法，另一個就是用試除法：檢驗每個數(shù)是不是質(zhì)數(shù)，是的話就把它塞進質(zhì)數(shù)表里。
歐幾里得篩法是這樣的：要得到2~n之間的所有質(zhì)數(shù)，寫下2~n之間的所有整數(shù)，然后找數(shù)列中最小的數(shù)，也就是2；把2留下，刪掉所有2的倍數(shù)；再回過頭來，找到數(shù)列中最小的數(shù)3，刪掉所有3的倍數(shù)……如此反復，直到?jīng)]有數(shù)可刪為止。歸結(jié)起來，就是在2~n的整數(shù)中，不斷進行以下操作：找出最小的數(shù)m，刪除km（k>1，km<=n），最后剩下的就是質(zhì)數(shù)。
試除法更加直觀，直接拿一個數(shù)來判斷它是不是質(zhì)數(shù)：只要依次檢驗2~n-1之間是否有能整除n的數(shù)就可以了，只要有一個數(shù)能整除n，n就不是質(zhì)數(shù)。但這個辦法太笨，用時太多。對于n/2+1~n-1之間的數(shù)來說，顯然都不可能整除n，因此只需要用2~n/2來試除就行了。
但這就是最快的嗎？非也。實際上，再想一下可以發(fā)現(xiàn)。如果n能被m整除，則n必然也能被n/m整除；也就是說，如果n有一個約數(shù)為m，那它必然也會有一個約數(shù)n/m，于是就不需要再用n/m來試除了。當m*m=n時，m=n/m，所以只需要檢驗從2~sqrt(n)之間的數(shù)即可。由于出現(xiàn)了平方根，這樣需要試除的數(shù)就大為減少。
但這仍然不是最快的方法?；貞浺幌滦W時我們?nèi)绾闻袛噘|(zhì)數(shù)，并不是用2, 3,4…依次試除，而只是用一些質(zhì)數(shù)去試除。這樣有個問題就出來了：要判斷質(zhì)數(shù)，生成質(zhì)數(shù)表，但為了判斷質(zhì)數(shù)，又需要提前知道一些質(zhì)數(shù)以便來試除?？瓷先ビ行┟?。其實這個問題也非常好解決。
前面說過，判斷一個數(shù)n是否是質(zhì)數(shù)需要用2~sqrt(n)之間的數(shù)去試除；現(xiàn)在更進一步，只要用2~sqrt(n)之間的所有質(zhì)數(shù)去試除就行了。2~sqrt(n)之間的質(zhì)數(shù)如果得到呢？從之前質(zhì)數(shù)表里得到。于是，問題就轉(zhuǎn)化成了為了生成更大的質(zhì)數(shù)表，需要準備一個較小的質(zhì)數(shù)表，然后把判斷為是質(zhì)數(shù)的數(shù)逐個放進質(zhì)數(shù)表里去，生成更大的質(zhì)數(shù)表。初始時，質(zhì)數(shù)表里有一些元素。
以下我寫了一個小程序，用來生成并輸出100000個質(zhì)數(shù),運行時間會比較長，那是因為時間都浪費在輸出上了，其實計算只需要1秒不到。
代碼如下：
#include<iostream>
#include<math.h>
#define N 100000 //生成100000個質(zhì)數(shù)
using namespace std;
int prime[N]; //一個全局數(shù)組，用來保存質(zhì)數(shù)表
void makeprime()//生成質(zhì)數(shù)表的子函數(shù)
{int j,n=29,i=9,sqrtn;//從第10個質(zhì)數(shù)開始計算，第10個質(zhì)數(shù)是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個質(zhì)數(shù)在表中
while (i<N) //i是計數(shù)變量
{
j=0; //每次從表頭開始試除
sqrtn=sqrt(n); //n的平方根
while (prime[j]<=sqrtn)
{
if (n%prime[j]==0)break; //若n能整除質(zhì)數(shù)表中的某數(shù)，則跳出
j++;
}
if (prime[j]>sqrtn){prime[i]=n; i++;}
n+=2; //除了2，偶數(shù)不會是質(zhì)數(shù)，因此跳過所有偶數(shù)
}
}
int main()
{
makeprime();
for (int i=1;i<N;i++)
{cout<<prime[i-1]<<""; if(i%10==0)cout<<endl;}//每輸出10個數(shù)換行
system("pause");
return 0;}
