练46.3 哥德巴赫猜想

解题思路

定义prime函数。对每个偶数s=4～n，从2起枚举p到s/2，找到p与s-p都为质数就输出第一组。若枚举完仍没有，输出验证失败。

正确性说明

计算规则直接来自题目定义。按所述顺序处理时，已完成部分的结果被准确保存在累加量、计数或当前状态中；下一步只加入新增贡献。最终得到完整要求的结果。

易错点

质数函数排除1；每个偶数只输出一组，样例采用较小加数最小的组。

复杂度

直接枚举上界时间O(n²√n)，空间O(1)。

参考代码（C++11）

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

bool prime(int x) {
    if (x < 2)
        return false;
    for (int d = 2; d * d <= x; d++)
        if (x % d == 0)
            return false;
    return true;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int s = 4; s <= n; s += 2) {
        bool found = false;
        for (int p = 2; p <= s / 2; p++)
            if (prime(p) && prime(s - p)) {
                cout << s << "=" << p << "+" << s - p << "\n";
                found = true;
                break;
            }
        if (!found)
            cout << "验证失败！\n";
    }
    return 0;
}