哥德巴赫猜想驗證：計算偶數拆分為兩質數之和的組合數

問題描述

對於每個輸入的偶數 n (4 ≤ n < 2^15 = 32768)，計算有多少對本質不同的質數對 (p1, p2) 滿足 p1 + p2 = n 且 p1 ≤ p2。輸入以 0 結束。

算法：埃拉托斯特尼篩法 + 雙指針/集合查找

步驟 1：預計算質數表

最大 n = 32767，質數上限同此。用篩法 O(N log log N) 生成所有質數及 isPrime[] 布爾數組。

步驟 2：計數邏輯

對於每個 n：

• 遍歷質數 p1 從 2 到 n/2。
• 若 isPrime[n - p1] 為真，則 (p1, n-p1) 為一組合法分解，計數器++。
• 因遍歷至 n/2，自動保證 p1 ≤ p2，不重複計算。

C++ 參考實現

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 32768;
bool isPrime[MAXN];
vector<int> primes;

void sieve() {
    fill(begin(isPrime), end(isPrime), true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i < MAXN; ++i) {
        if (isPrime[i]) {
            for (int j = i * i; j < MAXN; j += i) isPrime[j] = false;
        }
    }
    for (int i = 2; i < MAXN; ++i) if (isPrime[i]) primes.push_back(i);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    sieve();
    int n;
    while (cin >> n && n != 0) {
        int count = 0;
        for (int p : primes) {
            if (p > n / 2) break;
            if (isPrime[n - p]) count++;
        }
        cout << count << "\n";
    }
    return 0;
}

Java 參考實現

import java.util.*;

public class Goldbach {
    static final int MAXN = 32768;
    static boolean[] isPrime = new boolean[MAXN];
    static List<Integer> primes = new ArrayList<>();

    static {
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i * i < MAXN; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j < MAXN; j += i) isPrime[j] = false;
            }
        }
        for (int i = 2; i < MAXN; i++) if (isPrime[i]) primes.add(i);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            if (n == 0) break;
            int count = 0;
            for (int p : primes) {
                if (p > n / 2) break;
                if (isPrime[n - p]) count++;
            }
            System.out.println(count);
        }
    }
}

複雜度分析

• 預處理篩法：O(MAXN log log MAXN) ≈ 3e4，極快。
• 單次查詢：遍歷質數至 n/2，質數個數 ~ n/ln(n)，最多 ~3000 次循環，O(π(n))。
• 總時間遠低於 1ms，空間 O(MAXN)。

樣例驗證

輸入:
6
10
12
0

輸出:
1  (6 = 3+3)
2  (10 = 3+7, 5+5)
1  (12 = 5+7)

優化技巧

• 位圖篩法：用 bitset 或 long[] 壓縮空間，提高緩存命中。
• 線性篩：O(N) 篩法同時得到最小質因子，適合更大範圍。
• 預計算答案：若測試用例極多，可預先計算所有偶數答案存入 ans[n]，查詢 O(1)。