Problem D - 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 false, but it is believed to hold for all
even numbers. Your task is to test the conjecture for specified
integers. Each line of input will consisted of a single interger
n; produce a corresponding line of output in the appropriate
form:
n is not the sum of two primes.
n is the sum of p1 and p2.
Sample Input:
57
12
Output Input:
57 is not the sum of two primes.
12 is the sum of 1 and 11.