ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1356. Something Easier

How to solve this problem? (-)
Posted by Victor Barinov (TNU) 20 Mar 2005 17:10
Re: How to solve this problem? (-)
Posted by Burunduk1 20 Mar 2005 20:33
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.

Greedy-based backtracking (+)
Posted by Dmitry 'Diman_YES' Kovalioff 20 Mar 2005 22:00
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 (+)
Posted by Veniamin 21 Mar 2005 23:14
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 (+)
Posted by Cybernetics Team 21 Mar 2005 23:21
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 (+)
Posted by Vit Demidenko 3 May 2009 12:18
21=19+2
Re: Greedy-based backtracking (+)
Posted by georgi_georgiev 4 Sep 2009 05:56
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 )