篩法

篩法是一種簡單檢定素數的算法。據說是古希臘的埃拉托斯特尼（Eratosthenes，約公元前274～194年）發明的，又稱埃拉托斯特尼篩法（sieve of Eratosthenes）。

基本介紹

• 中文名：篩法
• 外文名：sieve of Eratosthenes
• 含義：簡單檢定素數的算法
• 發明：埃拉托斯特尼

簡述

具體做法是：給出要篩數值的範圍n，找出n以內的素數p₁，p₂，p₃，......，p_k。先用2去篩，即把2留下，把2的倍數剔除掉；再用下一個素數，也就是3篩，把3留下，把3的倍數剔除掉；接下去用下一個素數5篩，把5留下，把5的倍數剔除掉；不斷重複下去......。

因為希臘人是把數寫在塗臘的板上，每要划去一個數，就在上面記以小點，尋求質數的工作完畢後，這許多小點就像一個篩子，所以就把埃拉托斯特尼的方法叫做“埃拉托斯特尼篩法”，簡稱“篩法”。

一個篩子，專門篩掉合數

步驟

詳細列出算法如下：

1. 列出2以後的所有序列：
2. 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
3. 標出序列中的第一個素數，也就是2，序列變成：
4. 23 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
5. 將剩下序列中，劃摽2的倍數（用刪除線標出），序列變成：
6. 2 34567 891011 12 13 14 15 16 17 18 19 20 21 22 23 24 25
7. 如果現在這個序列中最大數小於最後一個標出的素數的平方，那么剩下的序列中所有的數都是素數，否則回到第二步。
8. 本例中，因為25大於2的平方，我們返回第二步：
9. 剩下的序列中第一個素數是3，將主序列中3的倍數劃出（刪除線），主序列變成：
10. 2 3 4 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
11. 我們得到的素數有：2，3
12. 25仍然大於3的平方，所以我們還要返回第二步：
13. 現在序列中第一個素數是5，同樣將序列中5的倍數劃出，主序列成了：
14. 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
15. 我們得到的素數有：2 3 5 。
16. 因為25等於5的平方，跳出循環.

結論：去掉劃線的數字，2到25之間的素數是：2 3 5 7 11 13 17 19 23。

C++代碼實現

以下是利用篩法求100以內素數的代碼：

#include<cmath>#include<cstring>#include<iostream>using namespace std;int main(int argc, char* argv[]){    const int n = 100;    bool a[101];    int i, j;        memset(a, 1, sizeof(a));    a[1] = 0;    for(i = 2; i <= sqrt(n); i ++)    {        if(a[i])        {            for(j = 2; j <= n/i; j ++)            {                a[i*j] = 0;            }        }    }    for(i = 2; i <= n; i ++)    {        if(a[i]) cout << i << " ";    }    return 0;}