题目解析：哥德巴赫猜想方案数（偶数拆成两个素数之和）

一、题意梳理

• 输入一个大于 2 的偶数 $n$（$4 \le n \le 10^6$）。
• 求把 $n$ 写成两个质数之和的方案数；无序计数，即 $3+7$ 与 $7+3$ 算同一种。
• 样例：$n=4 \to 1$（$2+2$）；$n=10 \to 2$（$3+7$、$5+5$）。

二、关键观察

观察 1（去重）：任一方案 $\{p,\ n-p\}$ 中，恰有一个数 $\le n/2$（相等时 $p=n/2$ 只出现一次）。因此只枚举较小的那个素数 $p \in [2,\ \lfloor n/2 \rfloor]$，检查 $n-p$ 是否也是素数，即可做到不重不漏。

观察 2（需要批量判素）：枚举过程中要对约 $n/2$ 个数判素。若每次用 $O(\sqrt{n})$ 试除，总代价 $\approx \frac{n}{2}\sqrt{n} \approx 5\times10^8$，在 $n=10^6$ 下太慢。正确做法是先用埃氏筛（或线性筛）一次性预处理 $[2, n]$ 内所有素数，之后 $O(1)$ 查表。

三、算法流程

1. 埃拉托斯特尼筛：isPrime[0]=isPrime[1]=false；从 2 起，把每个素数的倍数（从 $i^2$ 开始）标记为合数。复杂度 $O(n \log\log n)$。
2. 统计：for p = 2 .. n/2，若 isPrime[p] && isPrime[n-p] 则答案 +1。复杂度 $O(n)$。

四、参考代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000000 + 5;
bool isPrime[MAXN];

int main(){

    int n;
    cin >> n;

    // ① 埃氏筛：预处理 [0, n] 的素数表（筛到 n 即可，因为 n-p <= n-2）
    fill(isPrime, isPrime + n + 1, true); //全部重置为true
    isPrime[0] = isPrime[1] = false;          // 0、1 不是素数
    for(int i = 2; i * i <= n; i++)
        if(isPrime[i])
            for(int j = i * i; j <= n; j += i)
                isPrime[j] = false;

    // ② 只枚举较小的素数 p（p <= n/2），避免重复计数
    int cnt = 0;
    for(int p = 2; p <= n / 2; p++)
        if(isPrime[p] && isPrime[n - p])
            cnt++;

    cout << cnt << "\n";
    return 0;
}

五、样例验证

• $n=4$：$p=2$，$4-2=2$ 是素数 → 计 1。输出 1 ✓
• $n=10$：

  p	n−p	是否都素	计数
  2	8	8 非素	×
  3	7	✔	+1
  4	6	4 非素	×
  5	5	✔	+1
  输出 2 ✓