質數篩法實戰：埃拉托斯特尼篩法 C++ 實現與性能優化指南

前言

質數篩選是數論基礎運算。本文基於埃拉托斯特尼篩法，提供生產級 C++ 實現，分析時間空間複雜度，並給出位圖壓縮、輪因子優化、段式篩法三大進階方向，滿足從嵌入式小規模到服務端大規模 (10⁹+) 的不同需求。

一、經典篩法核心邏輯

從 2 開始，將每個質數的所有倍數標記為合數。未被標記者即為質數。

#include 
#include 
#include 

void sieve_classic(int max) {
    if (max < 2) return;
    std::vector is_composite(max + 1, false); // false = 可能是質數
    is_composite[0] = is_composite[1] = true;
    
    int limit = static_cast(std::sqrt(max));
    for (int i = 2; i <= limit; i++) {
        if (!is_composite[i]) {
            // 從 i*i 開始，步長 i
            for (int j = i * i; j <= max; j += i) {
                is_composite[j] = true;
            }
        }
    }
    // 輸出
    for (int i = 2, cnt = 0; i <= max; i++) {
        if (!is_composite[i]) {
            printf("%4d%c", i, (++cnt % 10 == 0) ? '\n' : ' ');
        }
    }
}

二、關鍵優化點解析

三、進階版：僅儲存奇數 + 位圖 (內存再降 2 倍)

void sieve_optimized(int max) {
    if (max < 2) { printf("2\n"); return; }
    int half = (max - 1) / 2; // 只存 3,5,7... 索引 k 對應數 2k+3
    std::vector is_comp(half, false);
    int limit = (static_cast(std::sqrt(max)) - 3) / 2;
    
    for (int i = 0; i <= limit; i++) {
        if (!is_comp[i]) {
            int p = 2 * i + 3; // 真實質數
            // p*p 對應索引: (p*p - 3)/2 = 2i² + 6i + 3
            for (int j = 2*i*i + 6*i + 3; j < half; j += p) {
                is_comp[j] = true;
            }
        }
    }
    printf("2 ");
    for (int i = 0, cnt = 1; i < half; i++) {
        if (!is_comp[i]) printf("%4d%c", 2*i+3, (++cnt % 10 == 0) ? '\n' : ' ');
    }
}

四、大規模場景 (n > 10⁸)：段式篩法

將 [2, n] 分塊 (如 32KB~1MB，適應 L1/L2 緩存)，逐塊篩選，僅需儲存基礎質數表 (至 √n) 和當前塊位圖。內存 O(√n + 塊大小)，緩存命中率極高，易於多線程並行。

五、工程選型決策表

六、現成輪子推薦

• primesieve (C++ 庫，GitHub)：當前最快開源質數篩庫，支持並行、段式、輪因子，10¹² 內質數計數秒級。
• GMP / OpenSSL：大整數質數測試 (Miller-Rabin)。

結語

埃拉托斯特尼篩法以「標記倍數」的簡單邏輯實現了 O(n log log n) 的近線性複雜度，是算法設計中「空間換時間、冗餘消除、緩存友好」思想的完美體現。根據規模選擇合適優化層級，或直接集成 primesieve，是工程師的理性選擇。