求素?cái)?shù)的算法及其復(fù)雜度分析

1、 求素?cái)?shù)的算法及其復(fù)雜度分析2008-04-05 17:46關(guān)于搜尋一定范圍內(nèi)素?cái)?shù)的算法及其復(fù)雜度分析 曾曉奇 關(guān)于素?cái)?shù)的算法是信息學(xué)競(jìng)賽和程序設(shè)計(jì)競(jìng)賽中?？嫉臄?shù)論知識(shí)，在這里我跟大家講一下尋找一定范圍內(nèi)素?cái)?shù)的幾個(gè)算法。看了以后相信對(duì)大家一定有幫助。 正如大家都知道的那樣，一個(gè)數(shù) n 如果是合數(shù)，那么它的所有的因子不超過(guò)sqrt(n)-n的開方,那么我們可以用這個(gè)性質(zhì)用最直觀的方法來(lái)求出小于等于n的所有的素?cái)?shù)。 num = 0; for(i=2; i<=n; i+) for(j=2; j<=sqrt(i); j+) if( j%i=0 ) break; if( j>sqrt(

2、i) ) primenum+ = i; /這個(gè)prime是int型，跟下面講的不同。 這就是最一般的求解n以內(nèi)素?cái)?shù)的算法。復(fù)雜度是o(n*sqrt(n)，如果n很小的話，這種算法（其實(shí)這是不是算法我都懷疑，沒有水平。當(dāng)然沒接觸過(guò)程序競(jìng)賽之前我也只會(huì)這一種求n以內(nèi)素?cái)?shù)的方法。-_-）不會(huì)耗時(shí)很多. 但是當(dāng)n很大的時(shí)候，比如n=10000000時(shí)，n*sqrt(n)>30000000000,數(shù)量級(jí)相當(dāng)大。在一般的機(jī)子它不是一秒鐘跑不出結(jié)果，它是好幾分鐘都跑不出結(jié)果，這可不是我瞎掰的，想鍛煉耐心的同學(xué)不妨試一試。 在程序設(shè)計(jì)競(jìng)賽中就必須要設(shè)計(jì)出一種更好的算法要求能在幾秒鐘甚至一秒鐘之內(nèi)找出n以

3、內(nèi)的所有素?cái)?shù)。于是就有了素?cái)?shù)篩法。 （我表達(dá)得不清楚的話不要罵我，見到我的時(shí)候扁我一頓我不說(shuō)一句話。） 素?cái)?shù)篩法是這樣的： 1.開一個(gè)大的bool型數(shù)組prime，大小就是n+1就可以了.先把所有的下標(biāo)為奇數(shù)的標(biāo)為true,下標(biāo)為偶數(shù)的標(biāo)為false. 2.然后： for( i=3; i<=sqrt(n); i+=2 ) if(primei) for( j=i+i; j<=n; j+=i ) primej=false; 3.最后輸出bool數(shù)組中的值為true的單元的下標(biāo)，就是所求的n以內(nèi)的素?cái)?shù)了。 原理很簡(jiǎn)單，就是當(dāng)i是質(zhì)(素)數(shù)的時(shí)候，i的所有的倍數(shù)必然是合數(shù)。如果i已經(jīng)被判斷

4、不是質(zhì)數(shù)了，那么再找到i后面的質(zhì)數(shù)來(lái)把這個(gè)質(zhì)數(shù)的倍數(shù)篩掉。 一個(gè)簡(jiǎn)單的篩素?cái)?shù)的過(guò)程：n=30。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 第 1 步過(guò)后2 4 . 28 30這15個(gè)單元被標(biāo)成false,其余為true。 第 2 步開始： i=3; 由于prime3=true, 把prime6, 9, 12, 15, 18, 21, 24, 27, 30標(biāo)為false. i=4; 由于prime4=false,不在繼續(xù)篩法步驟。 i=5; 由于prime5=true, 把pr

5、ime10,15,20,25,30標(biāo)為false. i=6>sqrt(30)算法結(jié)束。 第 3 步把prime值為true的下標(biāo)輸出來(lái)： for(i=2; i<=30; i+) if(primei) printf("%d ",i); 結(jié)果是 2 3 5 7 11 13 17 19 23 29 這就是最簡(jiǎn)單的素?cái)?shù)篩選法，對(duì)于前面提到的10000000內(nèi)的素?cái)?shù)，用這個(gè)篩選法可以大大的降低時(shí)間復(fù)雜度。把一個(gè)只見黑屏的算法優(yōu)化到立竿見影，一下就得到結(jié)果。關(guān)于這個(gè)算法的時(shí)間復(fù)雜度，我不會(huì)描述，沒看到過(guò)類似的記載。只知道算法書上如是說(shuō)：前幾年比較好的算法的復(fù)雜度為o(n),

6、空間復(fù)雜度為o(n(1/2)/logn).另外還有時(shí)間復(fù)雜度為o(n/logn),但空間復(fù)雜度為O(n/(lognloglogn)的算法。我水平有限啦，自己分析不來(lái)。最有說(shuō)服力的就是自己上機(jī)試一試。下面給出這兩個(gè)算法的程序：/最普通的方法：#include<stdio.h>#include<math.h> #define N 10000001int primeN;int main() int i, j, num = 0;for(i=2; i<N; i+) for(j=2; j<=sqrt(i); j+) if( j%i=0 ) break; if( j>

7、;sqrt(i) ) primenum+ = i; for(i=2; i<100; i+) /由于輸出將占用太多io時(shí)間，所以只輸出2-100內(nèi)的素?cái)?shù)?？梢园?00改為N if( primei )printf("%d ",i); return 0;/用了篩法的方法：#include<stdio.h>#include<math.h>#define N 10000001bool primeN;int main() int i, j; for(i=2; i<N; i+)if(i%2) primei=true;else primei=false;

8、 for(i=3; i<=sqrt(N); i+) if(primei) for(j=i+i; j<N; j+=i) primei=false; for(i=2; i<100; i+)/由于輸出將占用太多io時(shí)間，所以只輸出2-100內(nèi)的素?cái)?shù)。可以把100改為N if( primei )printf("%d ",i); return 0;裝了vc的同學(xué)上機(jī)跑一下這兩個(gè)程序試一試。這個(gè)差別，絕對(duì)是天上地下。前面那個(gè)程序絕對(duì)是n分鐘黑屏的說(shuō)。另外，對(duì)于這樣的篩法，還可以進(jìn)一步優(yōu)化，就是bool型數(shù)組里面只存奇數(shù)不存偶數(shù)。如定義primeN,則0表示3，1表示5

9、，2表示7，3表示9.。如果prime0為true,則表示3時(shí)素?cái)?shù)。prime3為false意味著9是合數(shù)。這樣的優(yōu)化不是簡(jiǎn)單的減少了一半的循環(huán)時(shí)間，比如按照原始的篩法，數(shù)組的下標(biāo)就對(duì)應(yīng)數(shù)。則在計(jì)算30以內(nèi)素?cái)?shù)的時(shí)候3個(gè)步驟加起來(lái)走了15個(gè)單位時(shí)間。但是用這樣的優(yōu)化則是這樣：則由于只存3 5 7 9 11 13 15 17 19 21 23 25 27 29，只需要14個(gè)單元第 1 步 把14個(gè)單元賦為true (每個(gè)單元代表的數(shù)是2*i+3,如第0單元代表3，第1單元代表5.)第 2 步開始： i=0; 由于prime0=true, 把 3, 6, 9, 12標(biāo)為false. i=1; 由于

10、prime1=true, 把 6, 11標(biāo)為false i=2 2*i+3>sqrt(30)算法結(jié)束。這樣優(yōu)化以后總共只走6個(gè)單位時(shí)間。當(dāng)n相當(dāng)大以后這樣的優(yōu)化效果就更加明顯，效率絕對(duì)不僅僅是翻倍。出了這樣的優(yōu)化以外，另外在每一次用當(dāng)前已得出的素?cái)?shù)篩選后面的數(shù)的時(shí)候可以一步跳到已經(jīng)被判定不是素?cái)?shù)的數(shù)后面，這樣就減少了大量的重復(fù)計(jì)算。（比如我們看到的，i=0與i=1時(shí)都標(biāo)了6,這個(gè)就是重復(fù)的計(jì)算。）我們可以發(fā)現(xiàn)一個(gè)規(guī)律，那就是3（即i=0）是從下標(biāo)為3的開始篩的，5（即i=1）是從下標(biāo)為11開始篩的（因?yàn)?已經(jīng)被3篩過(guò)了）。然后如果n很大的話，繼續(xù)篩。7（i=2）本來(lái)應(yīng)該從下標(biāo)為9開始篩，

11、但是由于9被篩過(guò)了，而16也已經(jīng)被5（i=1）篩過(guò)了。于是7（i=2）從23（就是2*23+3=49）開始篩。于是外圍循環(huán)為i時(shí)，內(nèi)存循環(huán)的篩法是從 i+(2*i+3)*(i+1)即i*(2*i+6)+3開始篩的。這個(gè)優(yōu)化也對(duì)算法復(fù)雜度的降低起到了很大的作用。相比于一般的篩法，加入這兩個(gè)優(yōu)化后的篩法要高效很多。高興去的同學(xué)可以試著自己編寫程序看一看效率。我這里有程序，需要的可以向我要。不懂得也可以問我。上面的素?cái)?shù)篩法是所有程序設(shè)計(jì)競(jìng)賽隊(duì)員都必須掌握的，而后面加了兩個(gè)優(yōu)化的篩法是效率很高的算法，是湖南大學(xué)huicpc39同學(xué)設(shè)計(jì)的（可能是學(xué)來(lái)的，也可能是自創(chuàng)的。相當(dāng)強(qiáng)悍）。在數(shù)量級(jí)更大的情況下就

12、可以發(fā)現(xiàn)一般篩法和優(yōu)化后的篩法的明顯區(qū)別。另外，臺(tái)灣的ACMTino同學(xué)也給我介紹了他的算法：a是素?cái)?shù)，則下一個(gè)起點(diǎn)是a*a,把后面的所有的a*a+2*i*a篩掉。這上面的所有的素?cái)?shù)篩選的算法都可以再進(jìn)一步化為二次篩選法，就是欲求n以內(nèi)的素?cái)?shù)，就先把sqrt(n)內(nèi)的素?cái)?shù)求出來(lái)，用已經(jīng)求得的素?cái)?shù)來(lái)篩出后面的合數(shù)。我把一般的篩選法的過(guò)程詳細(xì)的敘述了一遍，應(yīng)該都懂了吧？后面的優(yōu)化過(guò)程及不同的方法，能看懂最好。不是很難的。相關(guān)知識(shí)：最大公約數(shù)只有1和它本身的數(shù)叫做質(zhì)數(shù)（素?cái)?shù)）這個(gè)應(yīng)該知道吧？-_-b 至今為止，沒有任何人發(fā)現(xiàn)素?cái)?shù)的分布規(guī)律，也沒有人能用一個(gè)公式計(jì)算出所有的素?cái)?shù)。關(guān)于素?cái)?shù)的很多的有趣的

13、性質(zhì)或者科學(xué)家的努力我不在這里多說(shuō)，大家有興趣的話可以到百度或google搜一下。我在下面列出了一個(gè)網(wǎng)址，上面只有個(gè)大概。更多的知識(shí)需要大家一點(diǎn)一點(diǎn)地動(dòng)手收集。1.高斯猜測(cè)，n以內(nèi)的素?cái)?shù)個(gè)數(shù)大約與n/ln(n)相當(dāng)，或者說(shuō)，當(dāng)n很大時(shí)，兩者數(shù)量級(jí)相同。這就是著名的素?cái)?shù)定理。2.十七世紀(jì)費(fèi)馬猜測(cè)，2的2n次方+1，n=0，1，2時(shí)是素?cái)?shù)，這樣的數(shù)叫費(fèi)馬素?cái)?shù)，可惜當(dāng)n=5時(shí)，232+1就不是素?cái)?shù)，至今也沒有找到第六個(gè)費(fèi)馬素?cái)?shù)。3.18世紀(jì)發(fā)現(xiàn)的最大素?cái)?shù)是231-1，19世紀(jì)發(fā)現(xiàn)的最大素?cái)?shù)是2127-1，20世紀(jì)末人類已知的最大素?cái)?shù)是2859433-1，用十進(jìn)制表示，這是一個(gè)258715位的數(shù)字。4.孿生素?cái)?shù)猜想