1149: Goldbach's Conjecture

In 1742, Christian Goldbach, a German amateur mathematician, sent a letter to Leonhard Euler in which he made the following conjecture:
Every even number greater than 4 can be
written as the sum of two odd prime numbers.

For example:

8 = 3 + 5. Both 3 and 5 are odd prime numbers.
20 = 3 + 17 = 7 + 13.
42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23.

Today it is still unproven whether the conjecture is right. (Oh wait, I have the proof of course, but it is too long to write it on the margin of this page.)
Anyway, your task is now to verify Goldbach’s conjecture for all even numbers less than a million.


在1742年，德国的一个业余数学家Christian Goldbach给Leonhard Euler写信，在信中给出如下猜想（哥德巴赫猜想）：
每个大于4的偶数都可以写成两个奇素数的和。例如：8 = 3 + 5,3和5都是奇素数；而20 = 3 + 17 = 7 + 13； 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23。
现在哥德巴赫猜想仍然没有被证明是否正确。现在请证明对所有小于1000000的偶数，哥德巴赫猜想成立。

The input will contain one or more test cases.
Each test case consists of one even integer n with 6 <= n < 1000000.
Input will be terminated by a value of 0 for n.
输入包含一个或多个测试用例。每个测试用例给出一个偶整数n，6<=n<1000000。输入以0结束。

For each test case, print one line of the form n = a + b, where a and b are odd primes. Numbers and operators should be separated by exactly one blank like in the sample output below. If there is more than one pair of odd primes adding up to n, choose the pair where the difference b – a is maximized. If there is no such pair, print a line saying “Goldbach’s conjecture is wrong.”

对每个测试用例，输出形式为n = a + b，其中a和b都是奇素数，数字和操作符要用一个空格分开，如样例输出所示。如果有多于一对的奇素数的和为n，就选择b - a最大的一对。如果没有这样的数对，则输出“Goldbach's conjecture is wrong.”。

8
20
42
0

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