埃拉托斯特尼篩法求質數：原理與 C 語言實現

埃拉托斯特尼篩法

埃拉托斯特尼篩法 是一種古老而高效的質數篩選算法，時間複雜度接近 O(n log log n)，適合求解某個上限 N 以內的所有質數。

算法步驟

1. 創建一個長度為 N+1 的布爾數組 is_prime，初始全部標記為 true（索引 0、1 標記為 false）。
2. 從 2 開始遍歷到 √N：若 is_prime[i] 為 true，則將其所有倍數（從 i*i 開始）標記為 false。
3. 遍歷結束後，數組中仍為 true 的索引即為質數。

空間優化技巧：只存儲奇數

除 2 外所有質數均為奇數。可將數組元素僅對應奇數：索引 i 代表數值 2*i + 1。此法可將空間需求減半，在 16 位機器上尤為關鍵。

C 語言完整實現

#include <stdio.h>

void Eratosthenes(char *mark, int len) {
    // mark[0] 對應 3, mark[1] 對應 5 ... mark[i] 對應 2*i+3
    for (int i = 0; i < len; ++i) {
        if (mark[i]) { // 找到質數 p = 2*i+3
            int p = 2 * i + 3;
            // 從 p*p 開始標記，步長 2*p (保持奇數)
            // p*p 對應索引: (p*p - 3)/2 = (4*i*i + 12*i + 9 - 3)/2 = 2*i*i + 6*i + 3
            for (int j = 2*i*i + 6*i + 3; j < len; j += p)
                mark[j] = 0;
        }
    }
}

int main() {
    const int LIMIT = 10000;
    int len = (LIMIT - 1) / 2; // 只存奇數
    char *mark = (char*)calloc(len, 1); // 初始化為 0 (false), 稍後置 1
    for (int i = 0; i < len; ++i) mark[i] = 1;

    Eratosthenes(mark, len);

    printf("2 "); // 2 是唯一的偶質數
    int count = 1;
    for (int i = 0; i < len; ++i) {
        if (mark[i]) {
            printf("%d ", 2*i + 3);
            if (++count % 10 == 0) printf("\n");
        }
    }
    free(mark);
    return 0;
}

關鍵點解析

• 內層循環起始點：從 p*p 開始，因為更小的倍數已被更小的質數標記過。
• 步長：2*p，確保只遍歷奇數倍數，避免重複標記偶數。
• 字符數組：使用 char 而非 int 存儲標記，進一步節省內存。

擴展應用

該算法是線性篩（歐拉篩）的基礎，後者通過記錄最小質因子實現 O(n) 篩選，適合更大規模（如 10^7 以上）的質數生成場景。