最簡單的篩素數法方法就是從2開始，將所以2的倍數去掉，然後從3開始，將3的倍數去掉。根據這樣很容易寫出代碼，下面代碼就是是篩素數法得到100以內的素數並保存到primes[]數組中。
[cpp] //by MoreWindows( )
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;
}
}
//by MoreWindows( )
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;
}
}
可以看出這種會有很多重復訪問，如在訪問flag[2]和flag[5]時會各訪問flag[10]一次。因此最好想方法來減少這種重復訪問，讓flag[]數組的每個元素只被訪問一次。可以這樣考慮——簡單的篩素數法是利用一個素數的倍數必須不是素數，同樣任何一個數與其它所有素數的乘積必然也不是素數（這是因為每個合數必有一個最小素因子）。
為了試驗這種想法，先用2到10之間的數來驗證下。
2，3，4，5，6，7，8，9，10 初始時所以flag都是無標記的。
第一步 訪問2，flag[2]無標記所以將2加入素數表中，然後將2與素數表中的所有數相乘得到的數必定不是素數，2*2=4因此標記flag[4]。
2，3，4，5，6，7，8，9，10
第二步 訪問3，flag[3]無標記所以將3加入素數表中，將3與素數表中的所有數相乘得到的數必定不是素數，3*2=6，3*3=9因此標記flag[6]和flag[9]。
2，3，4，5，6，7，8，9，10
第三步 訪問4，flag[4]有標記所以4不加入素數表中，將4與素數表中的所有數相乘得到的數必定不是素數，4*2=8，4*3=12因此標記flag[8]。
2，3，4，5，6，7，8，9，10
第四步 訪問5，flag[5]無標記所以將5加入素數表中，將5與素數表中的所有數相乘得到的數必定不是素數，5*2=10，5*3=15因此標記flag[10]。
2，3，4，5，6，7，8，9，10
第五步 訪問6，flag[6]有標記所以6不加入素數表中，將6與素數表中的所有數相乘得到的數必定不是素數，6*2=12，6*3=18，6*5=30。
2，3，4，5，6，7，8，9，10
後面幾步類似，代碼不難寫出：
[cpp] //by MoreWindows( )
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;
}
}
//by MoreWindows( )
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;
}
}
這份代碼對不對了？仔細回顧下分析過程，可以發現有些數據還是被訪問多次了，這當然不是我們希望的結果，我們的要求是讓每個合數僅被它的最小素因子篩去一次。比如12，它的最小素因子是2，所以就只應該被在計算6*2時去訪問，而且不應該在計算4*3時去訪問，同理18也只應該被在計算9*2時去訪問，而且不應該在計算6*3時去訪問。
找到原因後，再來思考如何解決。6*3不行而9*2可以了，是因為6是2的倍數，所以在計算6*2之後就不能再將6與比2大的素數相乘，這些相乘的結果必定會導致重復計算。因此對於任何數來說，如果它如果是該素數的倍數那麼它就不能再與素數表中該素數之後的素數相乘了，如9是3的倍數，所以在9*3之後就不能再去用計算9*5了。因此在代碼中再增加一行判斷語句：
[cpp] //by MoreWindows( )
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) //這句保證每個非素數只被篩去一次
break;
}
}
}
//by MoreWindows( )
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) //這句保證每個非素數只被篩去一次
break;
}
}
}
想知道這二種篩素數法方法的區別嗎？現在對求2到1億之間的素數進行測試，看看區別到底會有多大，測試代碼如下：
[cpp] // 普通的篩素數方法與改進之後的效率對比
// by 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;
// 利用對每個素數的倍數必定不是素數來篩選
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;
}
}
// 利用了每個合數必有一個最小素因子來篩選
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的數據量下普通的篩素數方法與改進之後的效率對比\n", MAXN);
printf(" by MoreWindows( ) -- --\n\n");
clock_t clockBegin, clockEnd;
clockBegin = clock();
GetPrime_1();
clockEnd = clock();
printf("普通的篩素數方法\t%d毫秒\n", clockEnd - clockBegin);
clockBegin = clock();
GetPrime_2();
clockEnd = clock();
printf("改進的篩素數方法\t%d毫秒\n", clockEnd - clockBegin);
return 0;
}
// 普通的篩素數方法與改進之後的效率對比
// by 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;
// 利用對每個素數的倍數必定不是素數來篩選
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;
}
}
// 利用了每個合數必有一個最小素因子來篩選
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的數據量下普通的篩素數方法與改進之後的效率對比\n", MAXN);
printf(" by MoreWindows( ) -- --\n\n");
clock_t clockBegin, clockEnd;
clockBegin = clock();
GetPrime_1();
clockEnd = clock();
printf("普通的篩素數方法\t%d毫秒\n", clockEnd - clockBegin);
clockBegin = clock();
GetPrime_2();
clockEnd = clock();
printf("改進的篩素數方法\t%d毫秒\n", clockEnd - clockBegin);
return 0;
}
測試結果如圖所示：
可以看出，效率有4倍之差。改進還是比較可觀。有興趣的同學可以參考下一篇所講到的空間壓縮技巧來將改進後的篩素數法方進行空間壓縮。
文章最後作下小小總結：
1．普通的篩素數的原理是一個素數的倍數必須不是素數。
2．改進的篩素數的原理是每個合數必有一個最小素因子，根據每個最小素因子去訪問合數就能防止合數被重復訪問。
另外，篩素數法還有很多種改進手段，在數學論壇上可以去研讀一下，本文就不再深究了。
摘自 MoreWindows
