問(wèn)題描述
試編寫一個(gè)程序，找出 2→N 之間的所有質(zhì)數(shù)（質(zhì)數(shù)的概念請(qǐng)看這里），用盡可能快的方法實(shí)現(xiàn)。
問(wèn)題分析
這個(gè)問(wèn)題可以有兩種解法：一種是用“篩子法”，另一種是從 2→N 逐一檢測(cè)出質(zhì)數(shù)。如果要了解“篩法”，請(qǐng)看另一篇文章《求質(zhì)數(shù) 之 篩法》。
現(xiàn)在來(lái)介紹第二種方法。用這種方法，最先想到的就是讓從2→N逐一檢查。如果是就顯示出來(lái)，如果不是，就繼續(xù)檢查下一個(gè)直到超出范圍 N。這是正確的做法，但效率卻不高。當(dāng)然，2 是質(zhì)數(shù)，那么 2 的倍數(shù)就不是質(zhì)數(shù)，如果令 i 從 2→N，就很冤枉地測(cè)試了 4、6、8……這些數(shù)？所以第一點(diǎn)改建就是只測(cè)試 2 與所有的奇數(shù)就足夠了。同理，3 是質(zhì)數(shù)，但6、9、12……這些 3 的倍數(shù)卻不是，因此，如果能夠把 2 與 3 的倍數(shù)跳過(guò)去而不測(cè)試，任意連續(xù)的 6 個(gè)數(shù)中，就只會(huì)測(cè)試 2 個(gè)而已。以6n, 6n+1, 6n+2, 6n+3, 6n+4, 6n+5 為例，6n, 6n+2, 6n+4 是偶數(shù)，又 6n+3 是 3 的倍數(shù)，所以如果 2 與 3 的倍數(shù)都不理會(huì)，只要測(cè)試的數(shù)就只留下6n+1和6n+5而已了，因而工作量只是前面想法的 2/6 = 1/3，應(yīng)該用這個(gè)方法編程。
還有個(gè)問(wèn)題，就是如果判斷一個(gè)數(shù) i 是否為素?cái)?shù)。按素?cái)?shù)的定義，也就是只有 1 與本身可以整除，所以可以用 2→i-1 去除 i，如果都除不盡，i 就是素?cái)?shù)。觀點(diǎn)對(duì)，但卻與上一點(diǎn)一樣的笨拙。當(dāng) i>2 時(shí)，有哪一個(gè)數(shù)可以被 i-1 除盡的？沒(méi)有！為什么？如果 i 不是質(zhì)數(shù)，那么 i=a×b，此地 a 與 b 既不是 i 又不是 1；正因?yàn)?a>1，a 至少為 2，因此 b 最多也是 i/2 而已，去除 i 的數(shù)用不著是 2→i-1，而用 2→i/2 就可以了。不但如此，因?yàn)?i=a×b，a 與 b 不能大于 sqrt(i)，為什么呢？如果 a>sqrt(i)，b>sqrt(i)，于是 a×b > sqrt(i)*sqrt(i) = i，因此就都不能整除i了。如果i不是質(zhì)數(shù)，它的因子最大就是 sqrt(i)；換言之，用 2→sqrt(i)去檢驗(yàn)就行了。
但是，用 2→sqrt(i) 去檢驗(yàn)也是浪費(fèi)。就像前面一樣，2 除不盡，2 的倍數(shù)也除不盡；同理，3 除不盡，3 的倍數(shù)也除不盡……最理想的方法就是用質(zhì)數(shù)去除i。
但問(wèn)題是這些素?cái)?shù)從何而來(lái)？這比較簡(jiǎn)單，可以準(zhǔn)備一個(gè)數(shù)組 prime[]，用來(lái)存放找到的素?cái)?shù)，一開(kāi)始它里面有 2、3、5。檢查的時(shí)候，就用 prime[] 中小于 sqrt(i)的數(shù)去除 i 即可，如果都除不盡，i 就是素?cái)?shù)，把它放如 prime[] 中，因此 prime[] 中的素?cái)?shù)會(huì)越來(lái)越多，直到滿足個(gè)數(shù)為止！
不妨用這段說(shuō)明來(lái)編寫這個(gè)程序，但是程序設(shè)計(jì)的時(shí)候會(huì)有兩個(gè)小問(wèn)題：
- 如果只檢查 6n+1 和 6n+5 ？不難發(fā)現(xiàn)，它們的距離是4、2、4、2……所以，可以先定義一個(gè)變量 gab=4，然后 gab=6-gab;
- 比較是不能用 sqrt(i)，因?yàn)樗痪_。舉個(gè)例子，i=121，在數(shù)學(xué)上，sqrt(i) 自然是 11，但計(jì)算機(jī)里的結(jié)果可能是 10.9999999，于是去除的數(shù)就是 2、3、5、7，而不含 11，因此 121 就變成質(zhì)數(shù)了。解決這個(gè)問(wèn)題的方法很簡(jiǎn)單，不要用開(kāi)方，用平方即可。例如，如果 p*p<=i，則就用 p 去除 i。而且它的效率比開(kāi)方高。
程序清單
- #include <stdlib.h>
- #include <stdio.h>
- int creat_prime ( int prime[], int n, int total )
- {
- int i, *p, g = 2;
- for ( i = 7; i <= n; i += g ) {
- g = 6 - g;
- p = prime;
- while ( (*p) * (*p) <= i && i % (*p) ) {
- p++;
- }
- if ( i % (*p) ) {
- prime[total++] = i;
- }
- }
- return total;
- }
- int main(void)
- {
- int prime[30000] = { 2, 3, 5 };
- int total = 3;
- int n = 200000;
- int i;
- total = creat_prime ( prime, n, total );
- for ( i = 0; i < total; i++) {
- printf ( "%d ", prime[i] );
- if ( i && !(i % 10) )
- putchar ( '\n' );
- }
- putchar ( '\n' );
- return EXIT_SUCCESS;
- }
本文轉(zhuǎn)載自 :
版權(quán)聲明
本人的所有原創(chuàng)文章皆保留版權(quán)，請(qǐng)尊重原創(chuàng)作品。
轉(zhuǎn)載必須包含本聲明，保持本文完整，并以超鏈接形式注明原始作者“redraiment”和主站點(diǎn)上的本文原始地址。
聯(lián)系方式
我的郵箱，歡迎來(lái)信（redraiment@gmail.com）
我的Blogger（子清行）
我的Google Sites（子清行）
我的CSDN博客（夢(mèng)婷軒）
我的百度空間（夢(mèng)婷軒）