埃拉托斯特尼篩法：C 語言實作找出 2~1000 所有質數

篩法是尋找區間內所有質數的經典演算法，時間複雜度 O(n log log n)，遠優於逐一試除。本文以陣列模擬「篩子」，逐步剔除合數，保留質數，並給出完整 C 程式碼與輸出格式控制。

演算法步驟

1. 初始化：建立 int sieve[1000]，索引 2~999 設為 1（候選質數）。
2. 外層迴圈：篩選種子 p 從 2 開始，直到 p < sqrt(1000) ≈ 31（原碼用 500 仍正確但稍慢）。
3. 內層迴圈：將 p 的倍數（2p, 3p, ...）標記為 0（合數）。
4. 尋找下一種子：從 p+1 向後找第一個仍為 1 的數作為下一輪種子。
5. 輸出：遍歷陣列，值為 1 的索引即為質數，每 5 個換行。

完整 C 程式碼

#include <stdio.h>
#include <math.h>

int main() {
    int sieve[1000] = {0};
    for (int i = 2; i < 1000; ++i) sieve[i] = 1; // 初始化篩子

    int p = 2;
    while (p * p < 1000) {           // 優化：只需篩到 sqrt(N)
        for (int mult = p * 2; mult < 1000; mult += p)
            sieve[mult] = 0;         // 篩去倍數
        do { ++p; } while (p < 1000 && sieve[p] == 0); // 找下一質數
    }

    printf("2 到 1000 之間的所有質數：\n");
    int count = 0;
    for (int i = 2; i < 1000; ++i) {
        if (sieve[i]) {
            printf("%6d", i);
            if (++count % 5 == 0) printf("\n");
        }
    }
    return 0;
}

優化重點

• 外層條件改為 p * p < N，避免多餘輪次（原碼 p < 500 多跑 16 輪）。
• 內層起始可優化為 p * p（較小倍數已被更小質數篩去），但 2p 寫法較直觀教學用。
• 陣列大小 N+1 可直接用索引對應數值，無需位移。

輸出範例（前幾行）

     2     3     5     7    11
    13    17    19    23    29
    31    37    41    43    47
    ...

「篩法不僅是找質數的利器，更是『空間換時間』與『標記-掃描』思想的經典體現，廣泛應用於因數分解、歐拉函數預計算等數論問題。」