四个素数之和问题

Grade 0 Open Time Tuesday, 4 September 2012, 8:00 am
Discount 0.8 Time Discount Tuesday, 11 September 2012, 11:00 pm
Allow late Yes Close Time Sunday, 7 October 2012, 11:00 pm
Input file fourprime.in Output file fourprime.out

欧拉证明了素数有无穷多个这一经典数学理论。但是每个整数能表示成四个素数之和吗?希望你能帮我们高效地解决这一问题。在这个问题中,素数的定义为“一个素数是指一个正整数,且该正整数有且只有两个不同的因子”。例如37是一个素数,因为它只有两个不同的因子37和1。

输入

每行输入一个整数N(N<=10000000),这个数就是你需要把它表示成四个素数之和的数,输入0则表示结束。

输出

对于每个非零的输入,程序都有一个输出行,每行包含符号要求的四个素数。如果这个数不能表示为四个素数之和,那么输出一行“Impossible”。这里可能有多组解,任何一个合理的解都将被接受。