A Prime Conjecture

All submissions for this problem are available.
Chef has been exploring prime numbers lately, and has recently made a conjecture resembling
one of Goldbach's conjectures.
Chef's conjecture is that any odd number greater than 61 can be expressed as the sum of
a prime, a square of a prime, and a cube of a prime.
He wants you to help verify his conjecture for small numbers.
Note: negative numbers are never considered to be prime, nor are 0 and 1.
Input
Input will consist of a series of odd numbers greater than 61 and less than 10^{6},
one per line, terminated by the number 0 on a line by itself.
There will be at most 1000 lines.
Output
For each odd number in the input, print 3 primes P_{1}, P_{2}, P_{3} on a line,
where P_{1} + P_{2}^{2} + P_{3}^{3} is equal to the number from the input.
If no such primes exist, print "0 0 0" instead (quotes for clarity).
If there are multiple triplets of primes that satisfy the equation, print any such triplet.
Sample Input
81 85 155 0
Sample Output
5 7 3 73 2 2 5 5 5
Author:  pieguy 
Tester:  friggstad 
Editorial  http://discuss.codechef.com/problems/PRIMES2 
Tags  cook09 easy pieguy 
Date Added:  7042011 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.4, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions