日勿雨林

關於部落格
請前往新站:ian.twgg.org
  • 14079

    累積人氣

  • 0

    今日人氣

    0

    訂閱人氣

埃拉托斯特尼篩法


一、概念步驟:(轉自維基百科)

我們詳細列出演算法如下:

第一步,列出如下這樣以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

第二步,標出序列中的第一個質數,主序列變成:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

第三步,將剩下序列中,第二項開始每隔一項劃掉(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

第四步,如果現在這個序列中最大數小於第一個質數的平方,那麼剩下的序列中所有的數都是質數,否則返回第二步。

本例中,因為25大於2的平方,我們返回第二步:

剩下的序列中第一個質數是3,將主序列中3的倍數划出(紅色),主序列變成:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
我們得到的質數有:2,3。
25仍然大於3的平方,所以我們還要返回第二步:
現在序列中第一個質數是5,同樣將序列中5的倍數划出,主序列成了:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
我們得到的質數有:2 3 5 。
因為25等於5的平方,跳出循環.

結論:去掉紅色的數字,2到25之間的質數是:2 3 5 7 11 13 17 19 23。


二、以中文表示程式步驟:

  1. 定義整數陣列P,將所有元素設置為0。
  2. 設置i變量等於2。
  3. 如果 i>n ,算法結束。
  4. 如果P[i]等於0,那麼i是個質數。
  5. 對於所有 j ∈N,如果 i*j <=n,將陣列元素P[ i*j ]設置為1。
  6. 將i的值增加1,回到第3步。

三、用C語言算出150以內的質數:

#include <stdio.h>
#include <stdlib.h>

int main ()
{
        int  P[151], i, j;
        int  n = 150;

        for (i = 2; i <= n; i++)
                P[i] = 0;

        i = 2;

        while (i <= n) {
                if (P[i] == 0)
                        printf ("%i  ", i);

                j = 1;

                while (i * j <= n) {
                        P[i * j] = 1;
                        j++;
                }

                i++;
        }

        printf("n");
        system("PAUSE");
        return 0;
}


四、下載程式執行檔:

下載(EXE , 15.4 KB)
相簿設定
標籤設定
相簿狀態