HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaModerate

Project Euler #10 -- Summation of primes takes forever

Submitted by: @import:stackexchange-codereview··
0
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?

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 i that is a multiple of 2 but not 2, is not a prime. Consider upping i by 2 at a time, and starting sum off at 2. i would start at 3.



  • If something is divisible by 4, it's divisible by 2. Therefore, it's a good idea to make j iterate 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 certain i is a prime, you can stop at the point where jj is 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.