Обсуждение @ 1356. Чего бы попроще @ Timus Online Judge

Victor Barinov (TNU) How to solve this problem? (-) [8] // Задача 1356. Чего бы попроще 20 мар 2005 17:10

Burunduk1 Re: How to solve this problem? (-) // Задача 1356. Чего бы попроще 20 мар 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.

...and I had AC.

Dmitry 'Diman_YES' Kovalioff Greedy-based backtracking (+) [6] // Задача 1356. Чего бы попроще 20 мар 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

Veniamin Re: Greedy-based backtracking (+) [5] // Задача 1356. Чего бы попроще 21 мар 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!

Cybernetics Team Re: Greedy-based backtracking (+) // Задача 1356. Чего бы попроще 21 мар 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

Rustam Re: Greedy-based backtracking (+) [3] // Задача 1356. Чего бы попроще 13 ноя 2008 16:23

21 = 11+5+5

Vit Demidenko Re: Greedy-based backtracking (+) [2] // Задача 1356. Чего бы попроще 3 май 2009 12:18

21=19+2

georgi_georgiev Re: Greedy-based backtracking (+) [1] // Задача 1356. Чего бы попроще 4 сен 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 )
I hope this is helpful:)

Edric Mao Re: Greedy-based backtracking (+) // Задача 1356. Чего бы попроще 12 ноя 2011 20:21

May i ask why the presume is right??

Обсуждение задачи 1356. Чего бы попроще