Time Limit: 1000 ms Memory Limit: 65536 KiB
The Goldbach’s Conjecture is stated like the following:
Every even number greater than 4 can be written as the sum of two odd prime numbers.
Your task is now to verify Goldbach\'s Conjecture for all even numbers less than a million.
The input contains multiple test cases. Each test case consisted of an even integer n with 6 < n < 1000000. Input will be terminated by 0.
For every test case, print one line of the form “n = a + b”, a < b, without quotes. Where a and b are odd prime numbers. If there is more than one pair of odd primes, you are to print the pair a, b with the maximized difference b - a. If there are no such pair, print a line saying “Goldbach\'s conjecture is wrong.”.
8 20 0
8 = 3 + 5 20 = 3 + 17
In the second test case, you are not allowed to print “20 = 7 + 13”, because the difference between (7,13) is 6 and 6 is less than 17-3=14.