LeetCode 經典題解：Count Primes 質數計數 - 埃氏篩法與優化變體

編輯：關於C語言

Count Primes：統計小於 n 的質數個數 - 從試除法到埃氏篩法優化

給定非負整數 n，回傳小於 n 的質數數量。n 可達 10^6 量級，暴力試除法會超時，需使用篩法優化。

解法一：試除法優化版 (提交代碼)

核心觀察：判斷一數是否為質數，只需檢查能否被比它小的質數整除。

int countPrimes(int n) {
    if (n <= 2) return 0;
    if (n == 3) return 1;
    int primes[200] = {0}; // 假設 n < 10^6，質數個數 < 200 足夠
    int k = 0, count = 0;
    primes[k++] = 2; count = 1; // 2 是第一個質數
    
    for (int i = 3; i < n; i++) {
        bool isPrime = true;
        for (int j = 0; j < k; j++) {
            if (i % primes[j] == 0) { isPrime = false; break; }
        }
        if (isPrime) {
            if (k < 200) primes[k++] = i;
            count++;
            i++; // 關鍵優化：質數後的偶數必非質數 (除 2,3 外)，直接跳過
        }
    }
    return count;
}

時間複雜度約 O(n√n / log n)，對中等 n 可通過，但非最優。

解法二：埃拉托斯特尼篩法 - 標準最優解

時間複雜度 O(n log log n)，空間 O(n)，百萬級 n 毫秒級完成。

int countPrimes(int n) {
    if (n <= 2) return 0;
    bool *isComposite = (bool*)calloc(n, sizeof(bool)); // 全部初始為 false (質數)
    int count = 0;
    for (int i = 2; i * i < n; i++) { // 只需篩到 √n
        if (!isComposite[i]) {
            for (int j = i * i; j < n; j += i) // 從 i*i 開始標記
                isComposite[j] = true;
        }
    }
    for (int i = 2; i < n; i++)
        if (!isComposite[i]) count++;
    free(isComposite);
    return count;
}

關鍵優化點解析

外層迴圈至 √n：大於 √n 的合數必有小於 √n 的質因數，已被標記
內層從 i*i 開始：小於 i*i 的倍數已被更小質數標記 (如 2*5, 3*5 已被 2,3 標記)
位元組陣列優化：用 char 或位圖 (bit array) 降低記憶體 8 倍
只篩奇數：忽略偶數，空間再減半、速度提升 2 倍

進階變體：線性篩 (歐拉篩) O(n)

每個合數只被其最小質因數標記一次，彻底避免重複標記：

int countPrimes(int n) {
    vector<int> primes;
    vector<bool> isComposite(n, false);
    for (int i = 2; i < n; i++) {
        if (!isComposite[i]) primes.push_back(i);
        for (int p : primes) {
            if (i * p >= n) break;
            isComposite[i * p] = true;
            if (i % p == 0) break; // 核心：p 是 i 的最小質因數
        }
    }
    return primes.size();
}