P1579 哥德巴赫猜想（升级版）这道题，我见过不少人卡在同一个地方：素数判断都会写，但一遇到“输出字典序最小的一组”就开始乱。题目本身不复杂：给你一个奇数 n，找三个质数 a、b、c，满足 a ≤ b ≤ c 且 a + b + c = n，如果有多组解，输出字典序最小的那个。这篇题解适合刚学完筛法想找题练手的同学，也适合想复习“怎么把数学约束翻译成循环边界”的老手。我会把从读题、选算法、写代码到提交过题的全过程完整写下来，最后聊聊我在这个题上踩过的几个认知坑。

1. 题面拆解：“升级版”到底在考什么

1.1 从一条经典猜想变成一道可提交的题

哥德巴赫猜想在数论里流传很广，最常见的版本是“任意大于 2 的偶数都能表示成两个素数之和”，还有一个奇数版本：“任意足够大的奇数都能表示成三个素数之和”。P1579 这道题用的基本就是奇数版本，但加上了输出字典序最小的要求。

题目给你的 n 通常是 20000 以内的奇数。你不需要证明这个猜想，只需要在给定范围内验证，并且把一组具体的 a、b、c 构造出来。这其实是把“判断题”升级成了“构造题”：不只要回答能不能，还得把组合找出来。很多同学第一次做这题时还在纠结“怎么证明哥德巴赫猜想”，其实完全跑偏了——你只要让程序枚举出答案，就算完成任务。

1.2 容易被忽略的三个规则

第一，质数可以重复使用。很多人默认“三个质数互不相同”，结果漏掉了 2+2+(n-4) 这类解。题目里没有“互不相同”四个字，重复使用完全合法，只要每个数本身是质数。

第二，输出的三个数必须满足 a ≤ b ≤ c。如果你枚举出的是 7 7 3，排序成 3 7 7 也许能过，但如果不排序直接输出，顺序就错了。这里本质上是要输出一个有序三元组。

第三，字典序最小。先比 a，a 相同再比 b，再比 c。这个要求决定了枚举顺序，而不是找到任意一组解就输出。举个例子，n=17 时 2+2+13 和 3+7+7 都成立，但答案选 2 2 13，因为第一个数 2 < 3。这也是为什么很多题解里 a 从 2 开始枚举，而不是从 3 开始。

1.3 “升级版”到底升级在哪

如果把哥德巴赫猜想当成“偶数等于两个素数和”来验证，那只需要一层循环：枚举第一个素数，第二个用 n 减去第一个数，再判断是不是素数。搜索空间是 O(n)，非常轻松。

但换成“三个素数之和”，事情就微妙了。搜索空间从 O(n) 变成了 O(n²)，还要同时满足有序和字典序最小这两个约束。所以这道题真正考的不是什么高级算法，而是你能不能把一个数学条件精确地翻译成循环和边界。筛素数只是基本功，难点全在枚举顺序的设计上。

2. 枚举设计：为什么只枚举前两个质数就够了

2.1 三重循环为什么必然超时

如果脑子里第一时间想到“三个 for 循环，每个数从 2 试到 n”，那 n=20000 时的计算量是 8×10^12 次量级，跑完要等到天黑。

就算优化一下，只遍历质数而非所有整数，20000 以内的质数大约有 2200 个，三层循环仍然是 2200³ ≈ 10^10 量级，一样不可接受。所以这题的第一道坎不是“怎么判断素数”，而是“怎么减少循环层数”。

2.2 枚举前两个，第三个用减法确定

这是整道题最关键的一步：a 和 b 一旦定下来，c = n - a - b 就是唯一的，不需要第三层循环。你只需要判断这个 c 是不是质数。

把三重循环降成两重循环，核心思想是“减法消元”。这就好比三个人排队买票，你只知道总票价和前面两个人的票价，第三个人的票价就确定了，根本不需要挨个试。放到这道题里，就是枚举 a 和 b，然后查表判断 isPrime[c] 是否为真。

2.3 字典序最小如何靠枚举顺序保证

这题最容易被忽略的，就是“字典序最小”和“循环顺序”是绑定的。外层 a 从小到大枚举，内层 b 从 a 开始从小到大枚举，那么第一次命中的组合一定满足两个条件：

1. a 是所有可行解里最小的；
2. 在 a 相同的所有解里，b 是最小的。

由于先比 a 再比 b，这正好就是字典序最小的定义。所以实现时不需要额外存储所有解再排序，找到第一组就立刻输出。

为了直观，我们可以手动走一遍 n=13 的过程：a=2 时 b 从 2 开始试，2+2+9 不是质数，2+3+8 不是质数，2+5+6 也不是，直到 a=3、b=3、c=7，命中，输出 3 3 7。假如枚举顺序是乱的，就可能先找到 3+5+5，那就错了。

2.4 两个上界是怎么收缩出来的

因为要求 a ≤ b ≤ c，所以 a 最多只能到 n/3。理由很简单：如果 a > n/3，那么 b ≥ a > n/3，且 c ≥ b > n/3，三个数加起来一定超过 n，矛盾。

同理，a 固定之后，b 最多只能到 (n - a) / 2，因为 b ≤ c 等价于 b ≤ n - a - b，移项就是 2b ≤ n - a。

这两个上界不只是缩小枚举范围，还顺手解决了两个隐患。第一是保证 c ≥ b，不会出现“三个数都能拼出来但顺序不满足 a ≤ b ≤ c”的情况；第二是保证 c = n - a - b 永远不会变成负数，数组不会越界访问。

3. 筛法选型：20000 以内的素数表怎么一次备好

3.1 为什么不用 isPrime 函数现算

很多人的第一版代码是写一个isPrime(x)，每次循环都调用一遍。这确实能过小数据，但有两个问题：一是两重枚举里同一个数会被反复判定，重复计算很多；二是自己写判定函数时容易在i * i <= x这种边界上出错，比如漏掉等于号，或者i * i溢出 int。

筛法就不一样：一次预处理把 [2, n] 范围内所有素数标记好，后面每次判断 isPrime[x] 都是 O(1) 的查表。对 n=20000 来说，内存只开一个长度 n+1 的布尔数组，压力可以忽略不计。

3.2 埃氏筛的写法与关键细节

埃氏筛的思路很朴素：从 2 开始，把每个质数的倍数全部标记成合数。下面这段代码是竞赛里最常用的写法：

vector<bool> isPrime(n + 1, true); isPrime[0] = isPrime[1] = false; for (int i = 2; 1LL * i * i <= n; ++i) { if (isPrime[i]) { for (int j = i * i; j <= n; j += i) { isPrime[j] = false; } } }

有两个细节值得展开说。

第一，内层循环为什么从i * i开始，而不是从i * 2开始？因为i * 2、i * 3一直到i * (i - 1)，这些数在之前的循环里已经分别被 2、3 等更小的质因数标记过了。比如 i=5 时，5×2=10 早被 2 筛掉，5×3=15 早被 3 筛掉，5×4=20 也被 2 筛掉了，没必要再标一遍。直接从i * i开始是埃氏筛的经典优化。

第二，1LL * i * i这里为什么要写成 long long？因为如果哪天你把 n 改成 10^7，i 到 4000 附近时i * i就可能超出 int 范围。n=20000 不会有问题，但养成这个习惯能少踩一个坑。

3.3 进阶备选：欧拉筛和质数列表

如果以后遇到 n=10^6 甚至 10^7，埃氏筛依然能用，但欧拉筛是线性复杂度，并且顺带生成一个有序的质数列表 primes。欧拉筛的核心思想是保证每个合数只被它的最小质因子筛掉一次：

vector<int> primes; vector<bool> isPrime(n + 1, true); for (int i = 2; i <= n; ++i) { if (isPrime[i]) primes.push_back(i); for (int p : primes) { long long v = 1LL * i * p; if (v > n) break; isPrime[v] = false; if (i % p == 0) break; } }

有了 primes 列表之后，两重枚举可以改为直接遍历质数而不是遍历所有整数，能减少大量无谓的 isPrime 判断：

for (int ia = 0; ia < primes.size() && primes[ia] <= n / 3; ++ia) { int a = primes[ia]; for (int ib = ia; ib < primes.size() && primes[ib] <= (n - a) / 2; ++ib) { int b = primes[ib]; int c = n - a - b; if (isPrime[c]) { cout << a << " " << b << " " << c << endl; return 0; } } }

这个版本比全整数枚举更“竞赛化”，但理解起来会稍微绕一点。如果你第一次做这题，用埃氏筛加全整数枚举已经完全够了。

4. 完整代码与复杂度分析

4.1 可以直接提交的完整版

下面是我最后提交的版本，思路就是：埃氏筛建表 + 两重枚举 + 第一次命中即输出。代码里所有关键边界都用注释标出来了。

#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; // 1. 筛出 [2, n] 的素数表 vector<bool> isPrime(n + 1, true); isPrime[0] = isPrime[1] = false; for (int i = 2; 1LL * i * i <= n; ++i) { if (isPrime[i]) { for (int j = i * i; j <= n; j += i) { isPrime[j] = false; } } } // 2. 枚举 a，上界是 n/3 for (int a = 2; a <= n / 3; ++a) { if (!isPrime[a]) continue; // 3. 枚举 b，上界是 (n-a)/2，保证 c >= b for (int b = a; b <= (n - a) / 2; ++b) { if (!isPrime[b]) continue; int c = n - a - b; // 到这里 c 一定 >= b，且一定是非负数 if (isPrime[c]) { cout << a << " " << b << " " << c << endl; return 0; } } } return 0; }

这个代码的循环顺序就是字典序顺序：a 从小到大，b 从 a 开始从小到大。第一次找到的组合不需要和任何其他解比较，它就是字典序最小的。

4.2 复杂度账本

筛法部分是 O(n log log n)，n=20000 时几乎可以忽略。两重枚举的理论上界是我在第二章推导的 n/3 和 (n-a)/2 两个范围，总次数大概在 n²/12 量级，也就是约三千万次循环判断。

但实际跑起来会远小于这个值，因为有两个加速因素：一是循环里先if (!isPrime[a]) continue跳过了大量合数；二是因为哥德巴赫猜想的性质，往往很小的 a、b 组合就能命中，根本不需要遍历完所有组合。整体在 C++ 下 1 秒内跑完毫无压力。

4.3 用几个小数据走查搜索顺序

下面这几个例子可以帮你验证自己对枚举顺序的理解。括号里写的是搜索时“尝试过哪些组合之后才命中”。

注意 n=25 的情况，2+2+21 不成立是因为 21 不是质数；之后 2+7+16、2+11+12 等也都不成立。等到 a=3、b=3 时，c=19 是质数，才得到最小解。这正是“从小到大枚举、第一个命中即答案”的含义。

4.4 输入输出上的小习惯

数据范围这么小，用 cin/cout 完全没问题。习惯起见可以在 main 开头加一句ios::sync_with_stdio(false); cin.tie(0);。

输出格式要求是三个数中间用空格隔开，末尾换行。我见过有人输出成a b c后面多打了个空格，一般是没问题的，但最好还是写成cout << a << " " << b << " " << c << endl;这种标准写法。

5. 实战踩坑：为什么思路对还是会提交出错

5.1 从 3 开始枚举，丢掉含 2 的最小解

这是我见过最普遍的错误。很多人潜意识里觉得“三个质数相加，总该从奇数开始试吧”，于是外层循环写for (int a = 3; ...)，直接从 3 开始。

问题在于，一旦从 3 开始，2+2+(n-4) 这一整类解全被跳过了。比如 n=15 时，最小解是 2 2 11，但你从 3 开始枚举，得到的是 3+5+7，提交直接 WA。正确写法是 a 从 2 开始，因为 2 是最小的质数，也是合法可重复使用的质数。

5.2 找到解之后只用 break，外层还在跑

很多人内层循环写break，以为程序会停下来。实际上 break 只能跳出最内层循环，外层 a 的 for 还会继续，于是又找到第二组、第三组解，输出的答案可能变成“字典序第二大”甚至“最大”。

正确做法是找到后直接return 0;，结束整个 main 函数。如果不想用 return，也可以用bool found标记，然后在外层循环条件里加!found，效果一样。总之，别只写一个裸 break。

5.3 先排序三元组并不等于字典序最小

有同学觉得：我随便找一组 (7, 5, 3)，排个序变成 (3, 5, 7)，不就有序了吗？问题在于，排序只能让这一组数字从小到大排列，但 (2, 2, 13) 也是合法解，且字典序比 (3, 5, 7) 更小。你挑中的那一组根本就不是最小解，排序也不可能把它“变”成最小解。

所以“字典序最小”必须靠枚举顺序保证，而不是靠事后排序。这也是这题和普通“输出任意一组解”类题目的本质区别。

5.4 数组越界与负数下标

假设你没有采用 (n-a)/2 的上界，而是让 b 一路枚举到 n，那么 c = n - a - b 就可能变成负数。此时isPrime[c]访问的是isPrime[-1]之类的位置，轻则读脏数据，重则直接崩溃。

一个比较常见的修正是：内层循环里加一句if (c < b) break;。但更优雅的做法是直接用我前面写的上界b <= (n - a) / 2，这样 c 天然满足 c ≥ b ≥ 0，越界问题从源头就被消灭了。

5.5 不要把“n 是奇数”当废话

题目保证输入是合法范围内的奇数。有些同学为了“防御”，在程序里加了偶数分支，甚至对 n 取模判断，结果画蛇添足，输出了奇怪的东西。按题目约束写就行——奇数输入，奇数处理。如果你实在想防御，最多判断一下 n < 2 直接退出，别加多余逻辑。

6. 从这道题延伸出去：素数组合题的通用套路

6.1 通用套路：枚举前 k-1 个数，最后一个用差

两个数的情况：一层循环枚举 a，b = n - a，查表判断 isPrime[b]。三个数的情况：两层循环枚举 a、b，c = n - a - b，查表判断 isPrime[c]。推广到 k 个数：递归枚举前 k-1 个数，最后一个数用减法确定。

这套思路的本质是“消去最后一个自由变量”，适用于很多组合构造题。无论几个数，关键都一样：前面的数按字典序枚举，最后一个数用差来确定，最后再查表验证。

6.2 如果 n 变大，怎么调整

当 n 到 10^6 甚至 10^7 时，筛法依旧可行，内存也还够用。两重枚举虽然理论上变慢了，但因为第一组解通常出现得非常早，实际跑起来依然很快。如果想更稳，可以用 primes 列表遍历质数，而不是遍历整数，这样能把循环次数压得更低。

如果 n 再大，比如到 10^8 级别，布尔数组的内存就要认真算了，可能要用 bitset 压缩。不过那已经超出这类题的范畴，竞赛中很少会在一个“验证猜想”的题里把 n 给到这种规模。

6.3 提交前的小习惯

我每次写完筛法加枚举的题，都会先在本地跑几个小奇数，比如 11、15、25，手算出正确答案再对比。不要直接交上去靠评测机反馈来 debug，那样罚时很伤。这个小习惯帮我少交了不少无意义的 WA。

P1579 本身不算难，但它把“数学约束转换成代码边界”这个过程浓缩得特别典型：读题时想清楚质数可重复、输出有序、字典序最小；写代码时想清楚筛表怎么写、枚举上界怎么收缩、找到后怎么停。把这几点理清楚，这道题就能一次过。