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 at most two different positive integers. Your program must be very efficient. Note that we do not allow sums of equal prime numbers although the conjecture allows them.


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.


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!
n is the sum of p1 and p2.

For the second case, always make sure that (p2 - p1) is positive and minimized.

Sample Input


Sample Output

11 is not the sum of two primes!
12 is the sum of 5 and 7.

This challenge is provided by the ACM International Collegiate Programming Contest.

Upload Solution

Please log in to submit your solution.


Difficulty (6 votes)
Average test runtime 2.15
Points (changes over time) 50
Tried by 11 users
Solved by 4 users

Global ranking

# Name Runtime Points worth
1 ,s/java/NaN/gi 0.23 123
2 Justin 0.46 62
3 贝尔恩德 3.21 9
4 Jan 4.70 6