解题思路

1. 预处理素数表（筛法优化）

   • 使用**埃拉托斯特尼筛法（Eratosthenes Sieve）**预处理所有小于1,000,000的素数，并存储在一个布尔数组 is_prime 中，其中 is_prime[i] 表示 i 是否为素数。
   • 这样可以在O(1)时间内查询任意数是否为素数。

2. 枚举可能的素数对

   • 对于每个输入的偶数 n，从最小的奇素数 a = 3 开始，检查 a 和 n - a 是否均为素数。
   • 由于题目要求 b - a 最大，因此一旦找到第一个满足条件的 a，就可以直接输出结果（因为 a 从小到大遍历，第一个找到的 a 对应的 b = n - a 最大）。

3. 处理无解情况

   • 如果遍历完所有可能的 a 仍未找到解，则输出 "Goldbach's conjecture is wrong."（但根据哥德巴赫猜想，这种情况不会在 n ≥ 6 时发生）。

C++ 代码实现

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MAX_N = 1e6;

vector<bool> is_prime(MAX_N + 1, true);

// 埃拉托斯特尼筛法预处理素数表
void sieve() {
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= MAX_N; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= MAX_N; j += i) {
                is_prime[j] = false;
            }
        }
    }
}

int main() {
    sieve(); // 预处理素数表
    int n;
    while (cin >> n && n != 0) {
        bool found = false;
        // 从最小的奇素数3开始枚举
        for (int a = 3; a <= n / 2; a += 2) {
            if (is_prime[a] && is_prime[n - a]) {
                cout << n << " = " << a << " + " << n - a << endl;
                found = true;
                break;
            }
        }
        if (!found) {
            cout << "Goldbach's conjecture is wrong." << endl;
        }
    }
    return 0;
}