Goldbach and Euler

That every number which is resolvable into two prime numbers can be resolved into as many prime numbers as you like, can be illustrated and confirmed by an observation which you have formerly communicated to me, namely that every even number is a sum of two primes, and since n − 2) is also a sum of two prime numbers, n must be a sum of three, and also four prime numbers, and so on. If, however, n is an odd number, then it is certainly a sum of three prime numbers, since n−1) is a sum of two prime numbers, and can therefore be resolved into as many prime numbers as you like. However, that every number is a sum of two primes, I consider a theorem which is quite true, although I cannot demonstrate it. – Euler to Goldbach, 1742 The above conjecture about all numbers being the sum of two primes (where 1 counts as a prime) is not always true, but it is more true for even numbers. Your task is to test the conjecture for specified integers, considering that prime numbers are the numbers which are positive and divisible by exactly two positive integers. Your program must be very efficient. Input The input file contains 100000 lines of input. Each line contains a single integer n (0 < n ≤ 100000000). Input is terminated by end of file. Output For each line of input produce one line of output. This line should be of one of the following types: n is not the sum of two primes! nis the sum of p1and p2. For the second case, always make sure that (p2 − p1) is positive and minimized. Sample Input 11 12 Sample Output 11 is not the sum of two primes! 12 is the sum of 5 and 7.