P2038 [第六章习题2.3]Goldbach's Conjecture (哥德巴赫猜想)
描述
在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的偶数,哥德巴赫猜想成立。
每个大于4的偶数都可以写成两个奇素数的和。例如:8 = 3 + 5,3和5都是奇素数;而20 = 3 + 17 = 7 + 13; 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23。
现在哥德巴赫猜想仍然没有被证明是否正确。现在请证明对所有小于1000000的偶数,哥德巴赫猜想成立。
输入
输入包含一个或多个测试用例。每个测试用例给出一个偶整数n,6<=n<1000000。输入以0结束。
输出
对每个测试用例,输出形式为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