|
|
back to boardDuring 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?? |
|
|