patternjavaModerate
Project Euler #10 -- Summation of primes takes forever
Viewed 0 times
primesprojectforevereulersummationtakes
Problem
I have resolved the Problem presented in Project Euler #10:
The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.
But this code takes too long before producing a result, 12.4195167 minutes to be exact.
What should I do to optimize this code?
The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.
But this code takes too long before producing a result, 12.4195167 minutes to be exact.
What should I do to optimize this code?
public class summationOfPrimes{
public static void main(String args[]){
long sum=0;
outerloop:
for(int i=2;i<2000000;i++){
for(int j=2;j<=i;j++){
if(i!=j&&i%j==0){
continue outerloop;
}
else if(j==i){
sum=sum+i;
}
}
}
System.out.println(sum);
}
}Solution
Well, let's start with a few optimizations for you:
- Any
ithat is a multiple of 2 but not 2, is not a prime. Consider uppingiby 2 at a time, and starting sum off at 2.iwould start at 3.
- If something is divisible by 4, it's divisible by 2. Therefore, it's a good idea to make
jiterate through a list of already found primes - it's no use testing if something is divisible by 4 if it's not divisible by 2.
33 = 9. When you are checking whether a certainiis a prime, you can stop at the point wherejjis greater than the prime to test. For 7, you can stop at 3;3*3 = 9, after all.
Context
StackExchange Code Review Q#78215, answer score: 13
Revisions (0)
No revisions yet.