素數對猜想：孿生素數統計 C 語言篩法解法

素數對猜想：孿生素數統計 C 語言篩法解法

給定正整數 N (≤10⁵)，統計不超過 N 的**孿生素數對**個數（相差 2 的素數對，如 3-5, 5-7, 11-13）。本文提供基於埃拉托斯特尼篩法的 O(N log log N) 預計算 + O(1) 查詢解法，並分析優化技巧。

題目大意

• 輸入：N (1 < N ≤ 100000)。
• 輸出：滿足 `p` 和 `p+2` 均為素數且 `p+2 ≤ N` 的對數。
• 示例：N=10 → (3,5), (5,7) → 輸出 2。

算法思路：篩法預計算素數表

1. 建立 `is_prime[0..N]` 布爾數組，篩法標記所有素數。
2. 遍歷 3 到 N-2，若 `is_prime[i] && is_prime[i+2]` 則計數器++。
3. 輸出計數。

C 語言實現（標準篩法）

#include 
#include 
#include 
#include 

#define MAX_N 100000

bool is_prime[MAX_N + 1];

void sieve(int n) {
    memset(is_prime, true, sizeof(is_prime));
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= n; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }
}

int main() {
    int N;
    scanf("%d", &N);
    sieve(N);

    int count = 0;
    for (int i = 3; i + 2 <= N; i += 2) { // 只檢查奇數
        if (is_prime[i] && is_prime[i + 2]) {
            count++;
        }
    }
    printf("%d\n", count);
    return 0;
}

關鍵優化點

• 只處理奇數：除 2 外素數全為奇數，篩法內層步長 `2*i`，遍歷步長 2，內存/時間減半。
• 位圖壓縮：`bool` 佔 1 字節，用 `uint8_t` 每位存一奇數，內存再降 8 倍（N=10⁵ 時無壓力，大 N 必備）。
• 線性篩 (O(N))**：維护素數列表，每個合數只被最小質因子篩一次。代碼稍長但理論更優。

線性篩版本（進階）

int primes[MAX_N], cnt = 0;
bool is_composite[MAX_N + 1];

void linear_sieve(int n) {
    for (int i = 2; i <= n; i++) {
        if (!is_composite[i]) primes[cnt++] = i;
        for (int j = 0; j < cnt && i * primes[j] <= n; j++) {
            is_composite[i * primes[j]] = true;
            if (i % primes[j] == 0) break; // 核心：每個合數只標記一次
        }
    }
}

複雜度分析

數學背景：孿生素數猜想

• 猜想：存在無限多對孿生素數 (p, p+2)。
• 2013 年張益唐證明：存在無限多對素數差 ≤ 7000 萬（後改進至 246）。
• 尚未證明差為 2 的無限性，但計算機驗證極大範圍內成立。

測試用例

N = 10  → 2  (3-5, 5-7)
N = 20  → 4  (3-5, 5-7, 11-13, 17-19)
N = 100 → 8
N = 100000 → 1224 (參考值)

常見錯誤

1. **篩法上界錯**：`i*i <= n` 而非 `i <= n`。
2. **內層起點錯**：`j = i*i` 而非 `2*i`（小倍數已被小質數篩過）。
3. **統計邊界錯**：`i+2 <= N`，避免越界訪問 `is_prime[N+1]`。
4. **未處理 2**：2 和 4 不是孿生素數（4 非素數），從 3 開始步長 2 遍歷自動跳過。

總結

素數對猜想統計是**篩法預計算 + 線性掃描**的典型應用。掌握標準篩法與線性篩兩種實現，理解「只處理奇數、i*i 起篩、步長 2i」優化細節，即可高效解決百萬級以內素數統計問題。此模板直通「質數個數統計 (LeetCode 204)」、「質因數分解」、「互質對計數」等進階題型。