How to solve this problem? (-)
Re: How to solve this problem? (-)
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.
Greedy-based backtracking (+)
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
Re: Greedy-based backtracking (+)
What about 21? - it is odd number, however it can be presented by 2 numbers 2 and 19!!!
So, you idea is not right!
Re: Greedy-based backtracking (+)
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
Re: Greedy-based backtracking (+)
Posted by
Rustam 13 Nov 2008 16:23
21 = 11+5+5
Re: Greedy-based backtracking (+)
21=19+2
Re: Greedy-based backtracking (+)
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:)
Re: Greedy-based backtracking (+)
May i ask why the presume is right??
