【深基7.习4】哥德巴赫猜想

解题思路

先用埃氏筛标记 N 以内的质数。每个偶数 x 从 2 起递增枚举 p，找到 p 与 x-p 都为质数后立即输出。

正确性说明

筛法准确排除合数；第一次成功时 p 最小，因此得到题目指定分解。枚举全部偶数保证不遗漏。

易错点

输出不含额外空格，格式为 x=p+q；找到第一组就停止当前枚举。

复杂度

时间 O(N²+N log log N)，空间 O(N)；N≤10000。

参考代码（C++11）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<bool> prime(n + 1, true);
    prime[0] = prime[1] = false;
    for (int i = 2; i * i <= n; i++)
        if (prime[i])
            for (int j = i * i; j <= n; j += i)
                prime[j] = false;
    for (int x = 4; x <= n; x += 2)
        for (int p = 2; p <= x / 2; p++)
            if (prime[p] && prime[x - p]) {
                cout << x << "=" << p << "+" << x - p << "\n";
                break;
            }
    return 0;
}