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??