During the contest I also didn't know how to solve it.
I tried to submit dull solution:

1) 3 is enough.
2) The smallest prime number is not more than 500
3) The second prime number is not more than 50000
4) The biggest prime number is any.

...and I had AC.

Just remember that any even number can be presented as sum of two prime numbers, and any odd - as sum of 3 prime numbers.

P.S. As far as I know, this problem is known as Goldbach's Problem...

Edited by author 20.03.2005 22:01

What about 21? - it is odd number, however it can be presented by 2 numbers 2 and 19!!!
So, you idea is not right!

The idea stands for a maximum of 3 primes in decomposition; obviously that for an already prime number, its decomposition has only one prime, i.e. itself.
The Goldbach Conjecture, as I remember, stands that every even number >= 4 is decomposable into 2 primes

Edited by author 21.03.2005 23:23

21 = 11+5+5

21=19+2

He said can be... witch means that the number of primes for any n is 1, 2 or 3.
-if n is prime the answer is N
-else if n is even the answer are two numbers ( hint one if them is very small )
-else if n is odd
a) N can be presented as 2 and other prime number
b) N can be presented as sum of 3 prime numbers. The answer is 3 and solve( N - 3 ) (n - 3 is even => it is presented by 2 prime numbers )
I hope this is helpful:)

May i ask why the presume is right??