10168 - Summation of Four Primes

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

sive
New poster
Posts: 1
Joined: Wed Sep 17, 2003 12:58 pm

10168 - Summation of Four Primes

Post by sive » Wed Oct 08, 2003 3:21 pm

anybody got any tips to get me going on this?

thanks!

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

Post by Maarten » Wed Oct 08, 2003 9:25 pm

this problem is very easy if you know the following almost-theorem (the Goldbach Conjecture):

Every even number >= 4 can be written as the sum of two primes

My program ran in 1.5 seconds however; so it's pretty slow.. At the moment I'm precalculating primes up to 10000000 using the famous siff, and then just iterating through the primes to find an i such that both i and n-i are prime. Anyone knows how I can speed up ?

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Thu Oct 09, 2003 7:58 am

You don't have to compute primes in such range. It's neccessary to compute primes only to sqrt(1e7). :-) This speed up program to 0.2 sec or less :-) Mine execute in 0.16 sec.

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

Post by Maarten » Thu Oct 09, 2003 10:54 am

hmm... i don't understand it yet. Suppose I have to write the number N=10000000 as the sum of 4 primes. Then at least one of those primes should be bigger than N/4 = 2,500,000, which is a lot bigger than sqrt(N) = 3000...
So how can it be sufficient to compute only primes up to sqrt(N) ?

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Thu Oct 09, 2003 12:24 pm

You have right, but you can observe that such big number is prime when don't divide by any number less or equal than sqrt(N). So it's enough to compute prime numbers in range 1..sqrt(1e7).

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

Post by Maarten » Thu Oct 09, 2003 5:21 pm

I still don't understand. I assume your code would look something like this then (pseudocode):

Code: Select all

if( n%2 == 0 ) write "2 2"; n = n-4;
if( n%2 == 1 ) write "2 3"; n = n-5;
// now n is even so it can be written as the sum of two primes
for( int i=2; i<n; i++ )
  if( prime[i] && prime[n-i] ) write i, n+i; break;
So I have to know if i and n-i are prime.. am I right here ?

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia

Post by Joseph Kurniawan » Fri Oct 10, 2003 6:52 am

More less, yes. Only the difference is in the last line:
It should be "write i, n-i" instead of "write i, n+i".
This method cost me 0.059 sec.
There are 3 things one need to be successful : motivation, ability and chance. And if you're a believer, make it four : God's will.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Fri Oct 10, 2003 7:46 am

yes, and if you dont use big prime table - you got time as mine (0.16sec).
Instead of creating big table of prime numbers you can use linear algorithm checking if number is prime. :-)

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

Post by Maarten » Sat Oct 11, 2003 9:23 am

you found a linear (O(n)) time for checking if a number is prime??? I would VERY much like to know it, and i think *all* mathematicians and computer scientists would be interested as well!

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Mon Oct 13, 2003 8:51 am

Number N is prime only when is not divided by any prime number in range 2..sqrt(N). It's not any discovery :-)
You can calculate primes upto sqrt(1e7) because it's neccessary :-)

Best reagrds
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

Post by Dmytro Chernysh » Mon Oct 13, 2003 4:06 pm

Dominik, please, can you post a big(like 30-40 cases) input/output?
I don't know where is the mistake! :-( ...

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

Post by Maarten » Mon Oct 13, 2003 5:35 pm

Dominik, can you describe in detail how your algorithm works? I still don't understand your method...
If you want to find two primes k and l such that k + l = N, then at least one of them has to be bigger than (or equal to) N, right? So if I know primes up to sqrt(N) only, what does it help me? Of course, I can just try every integer i and test directly if both i and N-i are prime, I assume you use simple division algorithm for this. But why should this be faster than precalculating primes up to N? Especially if there are many test cases your method should be far slower.

By the way, i think your primality test is O(N), thus O(exp(n)) which is an exponential algorithm.

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

Post by Dmytro Chernysh » Mon Oct 13, 2003 7:02 pm

Dmytro_Chernysh wrote:Dominik, please, can you post a big(like 30-40 cases) input/output?
I don't know where is the mistake! :-( ...
No need to post test cases...
I've found my bug. It was like
8
2 2 2 2
10
3 3 2 2

Stupid mistakes :-(

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Tue Oct 14, 2003 8:01 am

Sorry for long delay - I was very busy ...
You have right - precalculating should be faster, but only in time, when input for problem will be very very huge. In other cases time which is needed for precalculating is very big ...
Yes, I use simple division algorithm.

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

Post by htl » Mon Jun 28, 2004 4:42 pm

I feel confused. There are 664579 prime numbers less than 10000000. If
I build a table including these numbers, every time I test a number, I
use only log664579/log2 (less than 25) times at worst by bsearch. It spends over 1sec. If I build a table including 446 prime numbers not greater than sqrt(1e7), I will use 446 times at worst to test a number to know if it's a prime. It spends less than 0.1sec. The latter way costs less time. Could someone tell me why?

Post Reply

Return to “Volume 101 (10100-10199)”