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