Goldbach

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

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.

Input

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.

Output

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.”.

Sample Input

8
20
0

Sample Output

8 = 3 + 5
20 = 3 + 17

Hint

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.

Source

zhengnanlee