LeetCode 204. 計數質數：埃拉托斯特尼篩法 C 語言優化實現

LeetCode 204. 計數質數：埃拉托斯特尼篩法 C 語言優化實現

統計小於非負整數 n 的質數個數。本文詳解經典「埃拉托斯特尼篩法」，並針對偶數優化、篩選起點優化、空間優化給出高效 C 語言實現，時間複雜度 O(n log log n)，空間 O(n)。

核心算法：埃拉托斯特尼篩法

1. 創建布爾數組 `isPrime[0..n-1]`，初始全部標記為質數（true）。
2. 0、1 非質數，標記 false。
3. 從 2 開始遍歷到 √n：若 `isPrime[i]` 為 true，則 i 是質數，將其所有倍數（從 i*i 開始）標記為合數。
4. 最終統計 `isPrime` 中 true 的個數。

關鍵優化點

• 偶數預處理：除 2 外所有偶數非質數，初始化時直接標記 false，計數器預減，主循環只處理奇數。
• 外層循環到 √n：若 i > √n，其倍數 i*i ≥ n，無需篩選。
• 內層從 i*i 開始：i * (i-1) 等更小倍數已被更小質數篩過。
• 步長 2i：對於奇數質數 i，其奇數倍數間隔 2i（偶數倍數已被排除）。

優化版 C 語言實現

#include <stdbool.h>
#include <stdlib.h>
#include <limits.h> // INT_MIN

int countPrimes(int n) {
    if (n <= 2) return 0;
    if (n == 3) return 1; // 只有 2

    // 1. 分配標記數組
    bool *isPrime = (bool*)malloc(n * sizeof(bool));
    if (!isPrime) return 0;

    // 2. 初始化：預設全為質數
    for (int i = 0; i < n; i++) isPrime[i] = true;
    isPrime[0] = isPrime[1] = false; // 0,1 非質數

    int count = n - 2; // 暫時計為 2..n-1 全質數

    // 3. 偶數預處理（2除外）
    for (int i = 4; i < n; i += 2) {
        isPrime[i] = false;
        count--;
    }

    // 4. 主篩選循環：只處理奇數
    for (int i = 3; i * i < n; i += 2) {
        if (isPrime[i]) {
            // 從 i*i 開始，步長 2i（跳過偶數倍數）
            for (int j = i * i; j < n; j += 2 * i) {
                if (isPrime[j]) {
                    isPrime[j] = false;
                    count--;
                }
            }
        }
    }

    free(isPrime);
    return count;
}

進一步空間優化：位圖/只存奇數

由於偶數（除 2）必合數，可只分配 `(n/2)` 大小數組，索引 `k` 對應數字 `2*k+1`。代碼略複雜，但空間減半。對於 n=10^7 級別，`bool[n]` 約 10MB，通常可接受。

複雜度分析

• 時間：O(n log log n) —— 經典篩法複雜度，優化後常數因子極小。
• 空間：O(n) —— `bool` 數組（1 字節/元素）。位圖可降至 O(n/8)。

測試用例

n = 10  → 4  (2,3,5,7)
n = 0   → 0
n = 1   → 0
n = 2   → 0
n = 3   → 1  (2)
n = 100 → 25

常見錯誤避坑

總結

計數質數是篩法的標志性應用。掌握「偶數預處理、√n 截斷、i*i 起篩、2i 步長」四大優化，即可寫出工業級高性能質數篩選代碼。此模板可直接擴展至「求第 k 個質數」、「質數因子分解」等進階問題。