GESP 题解库 / 5 级题解 / [GESP202609 五级] 哥德巴赫猜想 · 第 22 / 23 题
GESP202609 五级 · P17455 · 中等

哥德巴赫猜想

统计偶数 n 拆成两个质数之和的方案数(不计顺序)。

📊
n ≤ 10⁶
数值范围
🔢
int
数值类型
⚡
O(n log log n)
时间复杂度
🎯
埃氏筛 + 枚举
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

哥德巴赫猜想:任何大于 2 的偶数都能写成两个质数之和。如 4 = 2+2、6 = 3+3、8 = 3+5、10 = 3+7 = 5+5。

给定大于 2 的偶数 n,求把它写成两个质数之和的方案数。两种方案不同当且仅当包含的素数互不相同(即 10 = 3+7 与 10 = 7+3 算同一种)。

💡
人话翻译:枚举第一个质数 p,判断 n − p 是否也是质数。关键:只枚举 p ≤ n/2,这样每种方案只被数一次,自然满足了"不计顺序"的要求。判断质数用筛法预处理,做到 O(1) 查询。

🔍 关键词提取

埃氏筛质数判定枚举去重对称性

已知条件

项目说明
输入一个大于 2 的偶数 n
输出方案数
数据范围4 ≤ n ≤ 10⁶
方案定义n = p + q,p、q 均为质数
去重(p, q) 与 (q, p) 视为同一方案

需要解决的问题

02
思维导图
整理解题思路的全貌
🔢 筛表 + 枚举小的一半
📊 预处理
埃氏筛出 1~n 的质数
isP[x] 表示 x 是否质数
O(n log log n)
查询 O(1)
🔁 枚举
p 从 2 到 n/2
q = n − p
若 p 和 q 都是质数
计数加 1
✂️ 去重技巧
只枚举 p ≤ n/2
(p,q) 与 (q,p) 只算一次
不需要集合去重
自然满足"不计顺序"
⚠️ 易错点
枚举到 n 导致重复计数(答案翻倍)
漏判 q 的质数性
筛法数组开小
忘记 p 从 2 开始(1 不是质数)
03
样例手算推导
样例与几个小例子的验证

🧮 验证几个小偶数

先把小规模的方案列出来,确认理解正确。

n拆分方案(p ≤ q)方案数
42 + 21
63 + 31
83 + 51
103 + 7、5 + 52
125 + 71
143 + 11、7 + 72
1003+97、11+89、17+83、29+71、41+59、47+536
1
为什么 n = 10 是 2 种?

p 从 2 枚举到 n/2 = 5

p = 2:q = 8,8 不是质数 ✗

p = 3:q = 7,7 是质数 ✅(方案 3+7)

p = 4:4 不是质数 ✗

p = 5:q = 5,是质数 ✅(方案 5+5)

共 2 种

✅ 输出 2

2
如果枚举到 n 会怎样?

那样 3+7 和 7+3 会被分别数到

5+5 也会被数两次(p=5 时一次,p=5 还是同一次)

实际上 (3,7) 和 (7,3) 都会出现

答案会变成 3(多算了)

❌ 必须限制 p ≤ n/2

🔑
为什么"限制 p ≤ n/2"就能去重?因为每个合法方案 {p, q} 里,较小的那个一定 ≤ n/2。所以"让 p 走遍 ≤ n/2 的范围",每个方案恰好被枚举一次。这比"枚举全部再除以 2"更稳妥——因为 p = q = n/2 的情况只出现一次,直接除以 2 会错。

🧮 n = 100 的完整枚举

我们逐个检查 p ≤ 50 的情况。

pq = 100 − pp 是质数?q 是质数?计数
298✅❌ 98 是偶数—
397✅✅1
595✅❌ 95 = 5 × 19—
793✅❌ 93 = 3 × 31—
1189✅✅2
1387✅❌ 87 = 3 × 29—
1783✅✅3
1981✅❌ 81 = 9²—
2377✅❌ 77 = 7 × 11—
2971✅✅4
3169✅❌ 69 = 3 × 23—
3763✅❌ 63 = 7 × 9—
4159✅✅5
4357✅❌ 57 = 3 × 19—
4753✅✅6

n = 100 共有 6 种方案 ✓

⚠️
注意 p 只能取质数:比如 p = 4、6、8 等合数时根本不用检查 q,直接用 if (!isP[p]) continue; 跳过。这能省掉一半以上的检查。
04
解法对比
筛法 + 枚举 vs 逐个试除判质数

⚔️ 解法对比

🟢 筛法预处理 + 枚举(推荐) 推荐

先筛出质数表,再枚举 p ≤ n/2 查表

  • 时间 O(n log log n)
  • n = 10⁶ 时约 3 × 10⁶ 次
  • 每次查询 O(1)
  • 代码 20 行
💡
为什么必须筛:枚举阶段要做约 n/2 = 5 × 10⁵ 次质数判定,如果每次都试除到 √n,总复杂度会变成 O(n√n) ≈ 10⁹,必然超时。筛法把判定降到 O(1)。

🟠 每次试除判质数

枚举 p 时用试除法判断 p 和 q 是否为质数

  • 时间 O(n√n) ≈ 10⁹
  • 必然超时
  • 代码短但过不了
  • 典型的"想简单但不可行"
⚠️
量级对比:试除法每次判定要 √(10⁶) = 1000 次,乘以 5 × 10⁵ 次枚举,总共 5 × 10⁸ 次——即使 C++ 也极可能超时。

📈 性能对比

方案运算量(n = 10⁶)可行性
筛法 + 枚举约 3 × 10⁶✅ 稳过
试除判质数约 5 × 10⁸❌ 超时
05
算法流程图
筛质数表后枚举小数一侧
开始读入 n;用埃氏筛建立 isP[0..n]ans = 0p 从 2 到 n / 2isP[p] 为真吗?是 ✓检查 q否 ✗p 加 1isP[n − p] 为真吗?是 ✓ans 加 1否 ✗跳过输出 ans结束p 加 1 继续
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🔢 哥德巴赫拆分数

输入一个大于 2 的偶数,程序会列出所有拆分方案并计数。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

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

bool isP[1000005];

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

    // 埃氏筛:预处理 0 ~ n 的质数标记
    for (int i = 0; i <= n; i++) isP[i] = true;
    isP[0] = isP[1] = false;
    for (int i = 2; (long long)i * i <= n; i++) {
        if (isP[i])
            for (int j = i * i; j <= n; j += i) isP[j] = false;
    }

    int ans = 0;
    for (int p = 2; p <= n / 2; p++) {      // 只枚举较小的一半,天然去重
        if (!isP[p]) continue;
        int q = n - p;
        if (isP[q]) ans++;
    }

    printf("%d\n", ans);
    return 0;
}
🔑
为什么用 p <= n / 2 而不是 p <= n?这是本题去重的核心。每个方案 {p, q} 中较小的那个一定不超过 n/2,所以让 p 只走到 n/2,每个方案恰好被枚举一次。注意要用整数除法,写成 p <= n/2 对偶数 n 正好正确。

📖 关键几行怎么看

代码作用为什么这样写
isP[0] = isP[1] = false特殊值0 和 1 都不是质数
for (j = i * i; ...)筛法从 i² 开始标记,避免重复
p <= n / 2去重只枚举小的一半,避免重复计数
if (isP[q]) ans++判定同时要求 p 和 q 都是质数
⚠️
三个坑:① 枚举到 p <= n 导致答案翻倍;② 漏判 q 的质数性;③ 用试除法代替筛法(会超时)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
41题面样例 1:2 + 2
102题面样例 2:3+7、5+5
613 + 3
813 + 5
10063+97、11+89、17+83、29+71、41+59、47+53
1000000运行验证最大规模
✅
自查清单:① 用筛法了吗?② p 只枚举到 n/2 吗?③ 检查了 q 吗?

🚨 易错点清单

⚠️
枚举范围写错:必须只枚举 p ≤ n/2,否则 (p,q) 与 (q,p) 会被重复计数。
⚠️
漏判 q:必须确认 n − p 也是质数。
⚠️
用试除判质数:复杂度会到 10⁸ ~ 10⁹,必须用筛法。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n log log n)
空间复杂度
O(n)
n 最大
10⁶
运算量
约 3 × 10⁶

时间怎么算的?

空间都用在哪?

需要一个长度为 n + 1 的布尔数组。

✅ 约 300 万次操作,瞬间完成。关键是用筛法把质数判定降到 O(1)。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 埃氏筛模板
bool isP[N];
for (int i = 0; i <= n; i++) isP[i] = true;
isP[0] = isP[1] = false;
for (int i = 2; (long long)i * i <= n; i++)
    if (isP[i])
        for (int j = i * i; j <= n; j += i) isP[j] = false;

// 本题核心:只枚举较小的加数,天然去重
for (int p = 2; p <= n / 2; p++)
    if (isP[p] && isP[n - p]) ans++;

// 类似的"两数和"问题都可以用这个框架
// 例如:和为定值的两数之积最大、两数之差最小等
// 关键在于"用筛法预处理 + 枚举较小一侧"

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
埃氏筛O(1) 质数判定所有需要大量质数判断的题
枚举较小一侧天然去重两数之和/之差类问题
预处理换查询速度时间空间权衡多次查询的优化套路
🌟
思考题:如果题目改成"求所有方案中两个质数之差最大的那一组",要改哪里?(提示:p 越小则 q 越大、差越大。所以可以从 p = 2 开始枚举,找到第一个满足条件的 p 就停——不必数完所有方案,能提前退出。这说明同一套枚举框架可以做不同"目标"的优化。)