最簡單的篩素數(shù)法方法就是從2開始，將所以2的倍數(shù)去掉，然后從3開始，將3的倍數(shù)去掉。根據(jù)這樣很容易寫出代碼，下面代碼就是是篩素數(shù)法得到100以內(nèi)的素數(shù)并保存到primes[]數(shù)組中。

const int MAXN = 100; bool flag[MAXN]; int primes[MAXN / 3], pi; void GetPrime_1() {int i, j;pi = 0;memset(flag, false, sizeof(flag));for (i = 2; i < MAXN; i++)if (!flag[i]){primes[pi++] = i;for (j = i; j < MAXN; j += i)flag[j] = true;} }

?可以看出這種會有很多重復(fù)訪問，如在訪問flag[2]和flag[5]時會各訪問flag[10]一次。因此最好想方法來減少這種重復(fù)訪問，讓flag[]數(shù)組的每個元素只被訪問一次。可以這樣考慮——簡單的篩素數(shù)法是利用一個素數(shù)的倍數(shù)必須不是素數(shù)，同樣任何一個數(shù)與其它所有素數(shù)的乘積必然也不是素數(shù)（這是因為每個合數(shù)必有一個最小素因子）。

??? 為了試驗這種想法，先用2到10之間的數(shù)來驗證下。

?????? 2，3，4，5，6，7，8，9，10 ?????初始時所以flag都是無標(biāo)記的。

第一步 訪問2，flag[2]無標(biāo)記所以將2加入素數(shù)表中，然后將2與素數(shù)表中的所有數(shù)相乘得到的數(shù)必定不是素數(shù)，2*2=4因此標(biāo)記flag[4]。

?? 2，3，4，5，6，7，8，9，10

第二步 訪問3，flag[3]無標(biāo)記所以將3加入素數(shù)表中，將3與素數(shù)表中的所有數(shù)相乘得到的數(shù)必定不是素數(shù)，3*2=6，3*3=9因此標(biāo)記flag[6]和flag[9]。

?? 2，3，4，5，6，7，8，9，10

第三步 訪問4，flag[4]有標(biāo)記所以4不加入素數(shù)表中，將4與素數(shù)表中的所有數(shù)相乘得到的數(shù)必定不是素數(shù)， 4*2=8，4*3=12因此標(biāo)記flag[8]。

?? 2，3，4，5，6，7，8，9，10

第四步 訪問5，flag[5]無標(biāo)記所以將5加入素數(shù)表中，將5與素數(shù)表中的所有數(shù)相乘得到的數(shù)必定不是素數(shù)，5*2=10，5*3=15因此標(biāo)記flag[10]。

?? 2，3，4，5，6，7，8，9，10

第五步 訪問6，flag[6]有標(biāo)記所以6不加入素數(shù)表中，將6與素數(shù)表中的所有數(shù)相乘得到的數(shù)必定不是素數(shù)， 6*2=12，6*3=18，6*5=30。

? ?2，3，4，5，6，7，8，9，10

??? 后面幾步類似，代碼不難寫出：

const int MAXN = 100; bool flag[MAXN]; int primes[MAXN / 3], pi; void GetPrime_2() {int i, j;pi = 0;memset(flag, false, sizeof(flag));for (i = 2; i < MAXN; i++){if (!flag[i])primes[pi++] = i;for (j = 0; (j < pi) && (i * primes[j] < MAXN); j++)flag[i * primes[j]] = true;} }

?這份代碼對不對了？仔細(xì)回顧下分析過程，可以發(fā)現(xiàn)有些數(shù)據(jù)還是被訪問多次了，這當(dāng)然不是我們希望的結(jié)果，我們的要求是讓每個合數(shù)僅被它的最小素因子篩去一次。比如12，它的最小素因子是2，所以就只應(yīng)該被在計算6*2時去訪問，而且不應(yīng)該在計算4*3時去訪問，同理18也只應(yīng)該被在計算9*2時去訪問，而且不應(yīng)該在計算6*3時去訪問。

??? 找到原因后，再來思考如何解決。6*3不行而9*2可以了，是因為6是2的倍數(shù)，所以在計算6*2之后就不能再將6與比2大的素數(shù)相乘，這些相乘的結(jié)果必定會導(dǎo)致重復(fù)計算。因此對于任何數(shù)來說，如果它如果是該素數(shù)的倍數(shù)那么它就不能再與素數(shù)表中該素數(shù)之后的素數(shù)相乘了，如9是3的倍數(shù)，所以在9*3之后就不能再去用計算9*5了。因此在代碼中再增加一行判斷語句：

const int MAXN = 100; bool flag[MAXN]; int primes[MAXN / 3], pi; void GetPrime_2() {int i, j;pi = 0;memset(flag, false, sizeof(flag));for (i = 2; i < MAXN; i++){if (!flag[i])primes[pi++] = i;for (j = 0; (j < pi) && (i * primes[j] < MAXN); j++){flag[i * primes[j]] = true;if (i % primes[j] == 0) //這句保證每個非素數(shù)只被篩去一次break;}} }

?想知道這二種篩素數(shù)法方法的區(qū)別嗎？現(xiàn)在對求2到1億之間的素數(shù)進(jìn)行測試，看看區(qū)別到底會有多大，測試代碼如下：

// 普通的篩素數(shù)方法與改進(jìn)之后的效率對比 // by MoreWindows( http://blog.csdn.net/MoreWindows ) #include <stdio.h> #include <memory.h> #include <time.h> #include <math.h> const int MAXN = 100000000; bool flag[MAXN]; int primes[MAXN / 3], pi; // 利用對每個素數(shù)的倍數(shù)必定不是素數(shù)來篩選 void GetPrime_1() {int i, j;pi = 0;memset(flag, false, sizeof(flag));for (i = 2; i < MAXN; i++)if (!flag[i]){primes[pi++] = i;for (j = i; j < MAXN; j += i)flag[j] = true;} } // 利用了每個合數(shù)必有一個最小素因子來篩選 void GetPrime_2() {int i, j;pi = 0;memset(flag, false, sizeof(flag));for (i = 2; i < MAXN; i++){if (!flag[i])primes[pi++] = i;for (j = 0; (j < pi) && (i * primes[j] < MAXN); j++){flag[i * primes[j]] = true;if (i % primes[j] == 0)break;}} } int main() {printf(" 在%d的數(shù)據(jù)量下普通的篩素數(shù)方法與改進(jìn)之后的效率對比\n", MAXN);printf(" by MoreWindows( http://blog.csdn.net/MoreWindows ) -- --\n\n");clock_t clockBegin, clockEnd;clockBegin = clock();GetPrime_1();clockEnd = clock();printf("普通的篩素數(shù)方法\t%d毫秒\n", clockEnd - clockBegin);clockBegin = clock();GetPrime_2();clockEnd = clock();printf("改進(jìn)的篩素數(shù)方法\t%d毫秒\n", clockEnd - clockBegin);return 0; }

測試結(jié)果如圖所示：

??? 可以看出，效率有4倍之差。改進(jìn)還是比較可觀。還有空間壓縮技巧來改進(jìn)后的篩素數(shù)法方進(jìn)行空間壓縮。（位運算）

文章最后作下小小總結(jié)：

1．普通的篩素數(shù)的原理是一個素數(shù)的倍數(shù)必須不是素數(shù)。

2．改進(jìn)的篩素數(shù)的原理是每個合數(shù)必有一個最小素因子，根據(jù)每個最小素因子去訪問合數(shù)就能防止合數(shù)被重復(fù)訪問。

總結(jié)

以上是生活随笔為你收集整理的改进的筛素数法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。