1622：Goldbach’s Conjecture

题目描述

哥德巴赫猜想：任何大于 $4$ 的偶数都可以拆成两个奇素数之和。 比如：

• $8 = 3 + 5$
• $20 = 3 + 17 = 7 + 13$
• $42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23$

你的任务是：验证小于 $10^6$ 的数满足哥德巴赫猜想。

输入格式

多组数据，每组数据一个 $n$。

读入以 $0$ 结束。

输出格式

对于每组数据，输出形如 n = a + b，其中 $a, b$ 是奇素数。若有多组满足条件的 $a, b$，输出 $b - a$ 最大的一组。

若无解，输出 "Goldbach’s conjecture is wrong."。

样例

样例输入 #1

8
20
42
0

样例输出 #1

8 = 3 + 5
20 = 3 + 17
42 = 5 + 37

样例解释 #1

• $n=8$：$3+5=8$，且 $5-3=2$ 是最大差值（只有一组）。
• $n=20$：有 $3+17$ 和 $7+13$，差值分别为 $14$ 和 $6$，选择 $3+17$。
• $n=42$：有 $5+37$、$11+31$、$13+29$、$19+23$，差值分别为 $32$、$20$、$16$、$4$，选择 $5+37$。

数据范围

对于全部数据，$6 \le n \le 10^6$。

时空限制

• 时间限制：1000 ms
• 内存限制：524288 KB

注意：本题需要预处理 $10^6$ 以内的所有素数（可以用埃氏筛或线性筛）。然后对于每个偶数 $n$，从最小的奇素数 $3$ 开始枚举 $a$，检查 $a$ 和 $n-a$ 是否都是素数。由于要求 $b-a$ 最大，即 $a$ 尽可能小（因为 $b = n-a$，差值 $b-a = n-2a$，$a$ 越小差值越大），所以找到第一个满足条件的 $a$ 即可。注意 $a$ 和 $b$ 必须是奇素数，因此 $a$ 从 $3$ 开始，每次增加 $2$（因为偶数除了 $2$ 都不是素数，而 $2$ 是偶素数，但题目要求奇素数，所以 $a$ 不能是 $2$）。

如果找不到这样的 $a$，则输出错误信息。但根据哥德巴赫猜想，在 $n \le 10^6$ 范围内应该都有解。

时间复杂度：预处理素数 $O(N \log \log N)$，每次查询 $O(n)$ 枚举 $a$。由于 $n$ 最大 $10^6$，且多组数据，可能超时。优化：可以只枚举素数，而不是所有奇数。可以用一个布尔数组 is_prime 记录每个数是否为素数，然后枚举素数 $a$，直到 $a \le n/2$。因为如果 $a > n/2$，则 $b < a$，但我们可以要求 $a \le b$ 以避免重复，且差值最大时 $a$ 最小，所以 $a \le n/2$。