思路与算法

题意处理 $6\le n\le10^6$ 的偶数，多组输入以0结束。先对整个上界做埃氏筛，标记0、1非素数。若 $p$ 尚未标记，从 $p^2$ 起按步长 $p$ 标记合数；小于 $p^2$ 的合数倍数已有更小素因子处理过。保存所有奇素数的升序表。

对每个 $n$，从小到大枚举奇素数 $a\le n/2$，检查 $b=n-a$ 是否为素数。找到第一组便输出等式。因为 $b-a=n-2a$，固定 $n$ 时差随 $a$ 增大而减小，所以首个可行 $a$ 正好得到最大差。0只表示终止，不产生输出。若扫描后仍无合法分解，代码保留题目规定的失败输出分支；当前训练范围均为题意中的偶数，不用额外奇数查询补充原题定义。

正确性说明

筛法只把含素因子的非素数标记；任一合数有不超过其平方根的素因子，因此会被筛掉。未标记的至少2的数恰为素数。

任何由两个奇素数组成的分解都可把较小者记作 $a$，故 $a\le n/2$，一定在枚举范围内。每次检查保证两项均为奇素数且和为 $n$，所得分解合法。枚举按 $a$ 升序，第一组可行分解的 $a$ 最小，因 $b-a=n-2a$，它的差最大。若完全找不到，枚举完整性保证不存在分解。多组查询互不影响，直到0结束。

复杂度

设固定筛选上界 $M=10^6$，查询数为 $Q$。数组初始化与构建素数表为 $O(M)$，埃氏筛为 $O(M\log\log M)$。单次查询至多检查 $\pi(\lfloor n/2\rfloor)$ 个素数，故总时间可写为 $O(M\log\log M+\sum_q\pi(n_q/2))$，粗界为 $O(M\log\log M+Q\pi(M))$。额外空间 $O(M+\pi(M))=O(M)$，不保存全部查询。

易错点

1. 只能使用奇素数，枚举从3开始，不把2作为候选首项。
2. 要求最大差，而非任意分解或最近的一对；首个可行小素数最优。
3. 标记0和1，筛的起点为平方；终止0不输出。重复查询仍须逐行输出。
4. 输出等式包含等号、加号和两项；不要只输出数字对。样例、6、最大偶数和较长多组查询均核验。
5. 数据由独立试除素性判定复算，非官方隐藏数据。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    const int M = 1000000;
    vector<bool> bad(M + 1);
    bad[0] = bad[1] = true;
    for (int i = 2; i <= M / i; i++)
        if (!bad[i])
            for (int j = i * i; j <= M; j += i)
                bad[j] = true;
    vector<int> primes;
    for (int i = 3; i <= M; i += 2)
        if (!bad[i])
            primes.push_back(i);
    int n;
    while (cin >> n && n) {
        int first = -1;
        if (n % 2 == 0)
            for (int p : primes) {
                if (p > n / 2)
                    break;
                if (!bad[n - p]) {
                    first = p;
                    break;
                }
            }
        if (first < 0)
            cout << "Goldbach's conjecture is wrong.\n";
        else
            cout << n << " = " << first << " + " << n - first << '\n';
    }
}