统计偶数 n 拆成两个质数之和的方案数(不计顺序)。
哥德巴赫猜想:任何大于 2 的偶数都能写成两个质数之和。如 4 = 2+2、6 = 3+3、8 = 3+5、10 = 3+7 = 5+5。
给定大于 2 的偶数 n,求把它写成两个质数之和的方案数。两种方案不同当且仅当包含的素数互不相同(即 10 = 3+7 与 10 = 7+3 算同一种)。
n − p 是否也是质数。关键:只枚举 p ≤ n/2,这样每种方案只被数一次,自然满足了"不计顺序"的要求。判断质数用筛法预处理,做到 O(1) 查询。埃氏筛质数判定枚举去重对称性
| 项目 | 说明 |
|---|---|
| 输入 | 一个大于 2 的偶数 n |
| 输出 | 方案数 |
| 数据范围 | 4 ≤ n ≤ 10⁶ |
| 方案定义 | n = p + q,p、q 均为质数 |
| 去重 | (p, q) 与 (q, p) 视为同一方案 |
p ≤ q先把小规模的方案列出来,确认理解正确。
| n | 拆分方案(p ≤ q) | 方案数 |
|---|---|---|
| 4 | 2 + 2 | 1 |
| 6 | 3 + 3 | 1 |
| 8 | 3 + 5 | 1 |
| 10 | 3 + 7、5 + 5 | 2 |
| 12 | 5 + 7 | 1 |
| 14 | 3 + 11、7 + 7 | 2 |
| 100 | 3+97、11+89、17+83、29+71、41+59、47+53 | 6 |
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
那样 3+7 和 7+3 会被分别数到
5+5 也会被数两次(p=5 时一次,p=5 还是同一次)
实际上 (3,7) 和 (7,3) 都会出现
答案会变成 3(多算了)
❌ 必须限制 p ≤ n/2
{p, q} 里,较小的那个一定 ≤ n/2。所以"让 p 走遍 ≤ n/2 的范围",每个方案恰好被枚举一次。这比"枚举全部再除以 2"更稳妥——因为 p = q = n/2 的情况只出现一次,直接除以 2 会错。我们逐个检查 p ≤ 50 的情况。
| p | q = 100 − p | p 是质数? | q 是质数? | 计数 |
|---|---|---|---|---|
| 2 | 98 | ✅ | ❌ 98 是偶数 | — |
| 3 | 97 | ✅ | ✅ | 1 |
| 5 | 95 | ✅ | ❌ 95 = 5 × 19 | — |
| 7 | 93 | ✅ | ❌ 93 = 3 × 31 | — |
| 11 | 89 | ✅ | ✅ | 2 |
| 13 | 87 | ✅ | ❌ 87 = 3 × 29 | — |
| 17 | 83 | ✅ | ✅ | 3 |
| 19 | 81 | ✅ | ❌ 81 = 9² | — |
| 23 | 77 | ✅ | ❌ 77 = 7 × 11 | — |
| 29 | 71 | ✅ | ✅ | 4 |
| 31 | 69 | ✅ | ❌ 69 = 3 × 23 | — |
| 37 | 63 | ✅ | ❌ 63 = 7 × 9 | — |
| 41 | 59 | ✅ | ✅ | 5 |
| 43 | 57 | ✅ | ❌ 57 = 3 × 19 | — |
| 47 | 53 | ✅ | ✅ | 6 |
n = 100 共有 6 种方案 ✓
if (!isP[p]) continue; 跳过。这能省掉一半以上的检查。先筛出质数表,再枚举 p ≤ n/2 查表
枚举 p 时用试除法判断 p 和 q 是否为质数
| 方案 | 运算量(n = 10⁶) | 可行性 |
|---|---|---|
| 筛法 + 枚举 | 约 3 × 10⁶ | ✅ 稳过 |
| 试除判质数 | 约 5 × 10⁸ | ❌ 超时 |
输入一个大于 2 的偶数,程序会列出所有拆分方案并计数。
点按钮开始 →
#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 的质数性;③ 用试除法代替筛法(会超时)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
4 | 1 | 题面样例 1:2 + 2 |
10 | 2 | 题面样例 2:3+7、5+5 |
6 | 1 | 3 + 3 |
8 | 1 | 3 + 5 |
100 | 6 | 3+97、11+89、17+83、29+71、41+59、47+53 |
1000000 | 运行验证 | 最大规模 |
p ≤ n/2,否则 (p,q) 与 (q,p) 会被重复计数。n − p 也是质数。需要一个长度为 n + 1 的布尔数组。
✅ 约 300 万次操作,瞬间完成。关键是用筛法把质数判定降到 O(1)。
// 埃氏筛模板 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) 质数判定 | 所有需要大量质数判断的题 |
| 枚举较小一侧 | 天然去重 | 两数之和/之差类问题 |
| 预处理换查询速度 | 时间空间权衡 | 多次查询的优化套路 |