優化篩法求素數：基於 6k±1 規律的 C++ 高效實現

數學基礎：素數與 6 的關係

除 2 和 3 以外，所有素數都分布在 6 的倍數兩側，即形式為 6k-1 或 6k+1（k ≥ 1）。這是因為：

• 6k, 6k+2, 6k+4 為偶數（能被 2 整除）
• 6k+3 能被 3 整除
• 剩下的只有 6k+1 和 6k+5（即 6k-1）可能是素數

結合孿生素數定理：若 N-1 和 N+1 都是素數（孿生素數），則 N 必是 6 的倍數。

優化篩選算法流程

1. 預先標記 2、3 為素數
2. 只檢查形式為 6k-1 和 6k+1 的數
3. 篩選時步長優化：對於素數 p，從 p² 開始，步長為 2p（跳過偶數倍）
4. 利用位運算或字節數組壓縮存儲，節省內存

核心代碼實現

#include <cstdio>
#include <cmath>
#include <cstring>

char* GetPrimesLessN(int nSize) {
    char* flag = new char[nSize];
    memset(flag, 1, nSize);  // 1 表示可能是素數
    flag[0] = flag[1] = 0;   // 0,1 非素數

    // 標記 2 的倍數
    for (int i = 4; i < nSize; i += 2) flag[i] = 0;
    // 標記 3 的倍數
    for (int i = 6; i < nSize; i += 3) flag[i] = 0;

    int limit = (int)sqrt(nSize) + 1;
    for (int i = 5; i <= limit; i += 6) {  // 6k-1
        if (flag[i]) {
            for (int j = i * i; j < nSize; j += 2 * i) flag[j] = 0;
        }
        int ip1 = i + 2;  // 6k+1
        if (ip1 <= limit && flag[ip1]) {
            for (int j = ip1 * ip1; j < nSize; j += 2 * ip1) flag[j] = 0;
        }
    }
    return flag;  // 調用者負責 delete[]
}

int main() {
    const int LIMIT = 1000000;
    char* primes = GetPrimesLessN(LIMIT);
    int count = 0;
    for (int i = 2; i < LIMIT; ++i) if (primes[i]) ++count;
    printf("Primes < %d: %d\n", LIMIT, count);
    delete[] primes;
    return 0;
}

性能對比

進一步優化方向

• 輪因子篩：模 30 或 210 進一步減少候選數
• 分段篩：處理超大範圍（如 10^12 以內）時分塊處理
• 並行化：利用多線程並行篩選不同區間