Goldbach wrote a letter to Euler in 1742 suggesting that every integer n > 5 is the sum of three primes. Euler replied that this is equivalent to every even n > 2 is the sum of two primes ─ this is now know as Goldbach's conjecture.
Write a program that reads a sequence of integer numbers and verifies for each integer the initial suggestion made by Goldbach on his letter.
The input will consist of a series of integers, one integer per line. Each integer in the input file will be less than or equal to 1,000,000 and greater than 5. Input is terminated by a line with the number -1.
The output consists in an ordered sequence of three primes that verify the conjecture. From all the possible solutions we choose the one with the lowest first prime, and among these, the lowest second prime. The three prime numbers should be separated by one space with all three numbers on one line and with one line of output for each line of input.
2 2 2
2 7 491
2 19 999979