ENG  RUS Timus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

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

How to really solve this problem?
Послано Yuanming Yu 29 мар 2005 22:32
Acoording to Goldbach's problem, a even number can write as two prime numbers' sum(when n is not quite big,it is absolutely true)......

And an odd number can write as 3 + 2x, so our task is to solve when n is even......

But how to solve it fast?
I don't know.
I make an assume that the smaller prime is less than 100000...
I test some random number, it did produce an correct answer

So just search for the smaller prime and test whether the other one is prime or not......You can got AC......

But I am not sure, maybe my assume is wrong...
So, if some one can really solve it,say something.
Thanks.

Edited by author 29.03.2005 22:33
I think, you are right!
http://www.ieeta.pt/~tos/goldbach.html is worth seeing.

They are investigating the Goldbach conjecture there.
They say:
Let n be an even number larger than two, and let n=p+q, with p and q prime numbers, p<=q, be a Goldbach partition of n. In order to verify the Goldbach conjecture for a given n, it is sufficient to find one of its Goldbach partitions. Our strategy will be to find the minimal Goldbach partition, i.e., the one that uses the smallest possible prime number p.

They also say:
So far, we have tested all consecutive even numbers up to 2·10^17, and double-checked our results up to 10^17. Some extra intervals were also tested. About 157.3 CPU years were used to do all this. At least 28.2% of the work necessary to reach 10^18 is already done.

So, we may assume when solving this problem that the Goldbach conjecture is true. (It is because upper limit is only 10^9 which is much less than 10^17 :-).

> But how to solve it fast?
> I don't know.
>
Neither do I.
But I tried looking through all even numbers 2..100 000 000 and finding minimal Goldbach partitions for them. The maximal p that I had used was 1093.

More details:
2..100 000 000 -> maxP was 1093
2..10 000 000 -> maxP was 751
2..1 000 000 -> maxP was 523
2..100 000 -> maxP was 293
2..10 000 -> maxP was 173
2..1 000 -> maxP was 73
So, It doesn't seem to grow quickly... If I knew a suitable formula... I could have written a quicker solution.

Anyway, I got AC (http://acm.timus.ru/status.aspx?space=1&pos=867798). Details: 1356 Pascal Accepted 0.031 61 KB.

Please post anything you know on this topic. Are there better ways to find Goldbach partitions? Or are there better ideas on solving this problem?
Re: I think, you are right!
Послано Yu Yuanming 27 июн 2005 15:17
Well, there are about n/lnn prime in 1 .. n,so when I choose the smaller prime in 1 to 100000, it can almost guarantee that the answer always exist.
Re: How to really solve this problem?
Послано Sid 9 окт 2005 14:54
Special case:
6=3+3
but 9=2+7 not 9=3+3+3
Re: I think, you are right!
Послано Dzhulgakov Dmitry 20 июн 2006 02:20
I send similar solution and it got AC in 0.015 sek. You idea is right!

I used first two prime numbers less than 32000.

Edited by author 20.06.2006 02:21