篩選法求質數完全指南：從基礎埃拉托斯特尼篩到線性篩 O(n) 算法演進與 C 實現

問題定義

給定 N，求區間 [2, N] 內所有質數。質數：大於 1 且除 1 和自身外無其他因數的自然數。

算法演進路線圖

核心代碼實現 (C99)

版本 3：經典埃氏篩

void sieve_eratosthenes(int n, int **primes_out, int *count_out) {
    if (n < 2) { *count_out = 0; *primes_out = NULL; return; }
    char *is_composite = calloc(n + 1, 1); // 0: prime, 1: composite
    int *primes = malloc((n / 2 + 1) * sizeof(int)); // 上界
    int count = 0;
    for (int i = 2; i <= n; ++i) {
        if (!is_composite[i]) {
            primes[count++] = i;
            if ((long long)i * i <= n) // 防溢出
                for (int j = i * i; j <= n; j += i)
                    is_composite[j] = 1;
        }
    }
    *primes_out = realloc(primes, count * sizeof(int));
    *count_out = count;
    free(is_composite);
}

版本 4：奇數優化篩 (空間減半、速度提升 2x+)

void sieve_odd_only(int n, int **primes_out, int *count_out) {
    if (n < 2) { *count_out = 0; *primes_out = NULL; return; }
    int size = (n - 1) / 2; // 只存 3,5,7... 對應索引 i -> 數值 2*i+3
    char *is_comp = calloc(size, 1);
    int *primes = malloc((n / 2 + 1) * sizeof(int));
    int count = 0;
    primes[count++] = 2; // 2 是唯一偶質數
    for (int i = 0; i < size; ++i) {
        if (!is_comp[i]) {
            int p = 2*i + 3;
            primes[count++] = p;
            // 從 p*p 開始標記，步長 2p (保持奇數)
            long long start = 1LL * p * p;
            if (start > n) continue;
            for (long long j = start; j <= n; j += 2LL * p)
                is_comp[(j - 3) / 2] = 1;
        }
    }
    *primes_out = realloc(primes, count * sizeof(int));
    *count_out = count;
    free(is_comp);
}

版本 5：線性篩 (歐拉篩) — 理論最優 O(N)

void sieve_linear(int n, int **primes_out, int *count_out) {
    if (n < 2) { *count_out = 0; *primes_out = NULL; return; }
    char *is_comp = calloc(n + 1, 1);
    int *primes = malloc((n / 2 + 1) * sizeof(int));
    int count = 0;
    for (int i = 2; i <= n; ++i) {
        if (!is_comp[i]) primes[count++] = i;
        for (int j = 0; j < count && 1LL * i * primes[j] <= n; ++j) {
            is_comp[i * primes[j]] = 1;
            if (i % primes[j] == 0) break; // 核心：保證每個合數只被最小質因數標記
        }
    }
    *primes_out = realloc(primes, count * sizeof(int));
    *count_out = count;
    free(is_comp);
}

線性篩核心證明：為什麼 O(N)？

每個合數 x = i * p (p 為質數) 被標記的條件：

1. p 是 x 的最小質因數 (因為外層 i 從小到大，內層 p 從小到大)。
2. 當 p 整除 i 時 break，阻止更大的質數去標記 i * p (那時最小質因數會變成更大的質數，違反唯一性)。

因此每個合數**恰好被標記一次**，總操作數 ∑ (合數個數) = O(N)。

性能實測 (N = 10^7, Intel i7, -O2)

註：實際工程中 奇數優化篩常比線性篩更快** (常數因子小、緩存友好、無分支預測失誤)，線性篩優勢在極大 N (10^8+) 或需最小質因數分解時顯現。

工程級優化技巧

1. 位壓縮：uint8_t 每位存一個奇數，空間再減 8 倍 (N=10^9 需 ~60MB)。
2. 輪因子分解：跳過 2,3,5 的倍數 (模 30 周期)，空間再減 φ(30)/30 = 4/15。
3. 分段篩：大 N (10^12+) 分塊處理，只需 √N 空間，適合求區間質數。
4. 預計算小質數：const int small_primes[] = {2,3,5,7,11,13,17,19,23,29}; 手工展開前幾輪。
5. 並行化：分段篩天然適合多線程/OpenMP。

應用場景選型指南

完整可運行主程序模板

#include 
#include 
#include 
#include 

// 選擇一個實現
void sieve(int n, int **primes, int *count); // 實現見上文

int main() {
    int n = 10000000;
    int *primes; int count;
    clock_t t = clock();
    sieve(n, &primes, &count);
    t = clock() - t;
    printf("N=%d, primes=%d, time=%.3f ms\n", n, count, (double)t * 1000 / CLOCKS_PER_SEC);
    // 輸出前 10 個驗證
    for (int i = 0; i < 10 && i < count; ++i) printf("%d ", primes[i]);
    puts("");
    free(primes);
    return 0;
}

總結

從 O(N√N) 試除到 O(N) 線性篩，質數篩選算法展示了數論洞察 (最小質因數唯一性) 如何轉化為極致時間複雜度。工程實踐中，**奇數優化埃氏篩**以代碼簡潔、常數極小、緩存友好，成為 10^7 級以下首選；**線性篩**在需最小質因數分解、極大 N 或理論研究中不可替代。掌握兩者核心邏輯與優化技巧，是演算法工程師的基本功。