10168  Summation of Four Primes
Moderator: Board moderators
10168  Summation of Four Primes
anybody got any tips to get me going on this?
thanks!
thanks!
this problem is very easy if you know the following almosttheorem (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 ni are prime. Anyone knows how I can speed up ?
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 ni are prime. Anyone knows how I can speed up ?

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
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
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)
Born from ashes  restarting counter of problems (800+ solved problems)

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
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
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)
Born from ashes  restarting counter of problems (800+ solved problems)
I still don't understand. I assume your code would look something like this then (pseudocode):
So I have to know if i and ni are prime.. am I right here ?
Code: Select all
if( n%2 == 0 ) write "2 2"; n = n4;
if( n%2 == 1 ) write "2 3"; n = n5;
// 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[ni] ) write i, n+i; break;

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

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
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
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)
Born from ashes  restarting counter of problems (800+ solved problems)

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
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
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)
Born from ashes  restarting counter of problems (800+ solved problems)

 Experienced poster
 Posts: 146
 Joined: Sat Apr 26, 2003 2:51 am
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 Ni 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.
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 Ni 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.

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

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
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
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)
Born from ashes  restarting counter of problems (800+ solved problems)
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?
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?