ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1356. Something Easier

How to really solve this problem?
Posted by Yuanming Yu 29 Mar 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.

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!
Posted by Yu Yuanming 27 Jun 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?
Posted by Sid 9 Oct 2005 14:54
Special case:
but 9=2+7 not 9=3+3+3
Re: I think, you are right!
Posted by Dzhulgakov Dmitry 20 Jun 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