题目
歌德巴赫猜想的一种计算验证：对每个大于 4 的偶数 (n)，存在素数 (a,b) 使 (a+b=n)。本题额外要求：
- (a \le b)
- 在所有合法对中 (a \times b) 最大
输入：多行，每行一个偶数 (n)（(4 < n \le 20000)）
输出：对应的 a b
样例：
输入 输出
8 -> 3 5
10 -> 5 5
1000 -> 491 509
关键观察
在 (a+b=n) 且 (a\le b) 时，(b=n-a)，乘积 (a(n-a)) 是关于 (a) 的二次函数，对称轴在 (a=n/2)。因此 (a) 越靠近 (n/2)，乘积越大。
策略：从 (a=\lfloor n/2 \rfloor) 向下枚举，找到的第一对「(a) 与 (n-a) 都是素数」就是答案。
参考实现
#include <cstdio>
#include <cmath>
bool isPrime(int x) {
if (x < 2) return false;
if (x == 2) return true;
if (x % 2 == 0) return false;
int lim = (int)std::sqrt((double)x);
for (int i = 3; i <= lim; i += 2)
if (x % i == 0) return false;
return true;
}
int main() {
int n;
while (scanf("%d", &n) == 1) {
for (int a = n / 2; a >= 2; --a) {
int b = n - a;
if (a > b) continue;
if (isPrime(a) && isPrime(b)) {
printf("%d %d\n", a, b);
break;
}
}
}
return 0;
}
比旧代码更干净：不必手写「偶数就 --」的别扭循环，从中点递减即可。
复杂度
- 单次素数判定 (O(\sqrt{n}))
- 从中点向下最多试 (O(n)) 次，但实际很快命中
- (n\le 20000) 完全可过；若 (n) 到 (10^7) 级应预筛素数表
预筛优化（可选）
// 埃氏筛预处理 isPrime[0..N]
多组查询时收益明显。
小结
本题考的不是证明歌德巴赫，而是：约束下的搜索起点选择。乘积最大 ⇒ 从 (n/2) 往下找第一对素数解。写出正确的 isPrime 边界后，代码非常短。
正确性直觉
对偶数 (n)，从 (a=n/2) 向下找素数对，等价于在约束 (a+b=n) 下最大化 (a(n-a))。二次函数在中点取最大，故「中点往下第一对素数」即所求。
小优化
- 偶数 (n>2) 时，一个加数若为偶数只能是 2；可从奇数起跳
- 多组查询预筛素数表到 20000
和真正的猜想
本题是编程验证给定范围内的拆分，不是证明歌德巴赫猜想本身。数学上偶数哥德巴赫仍是著名问题；工程上我们只在有限 (n) 上找构造。