Efficient Sum of Primes

Question

I wrote this simple implementation of the sum of primes for the code eval

Challenge Description:

Write a program which determines the sum of the first 1000 prime numbers.

I would like to know of a better - more efficient - way of implementing the solution.

import java.lang.Math;

public class SumOfPrimes {

    public static boolean isPrime(int n) {
        if (n < 2) {
            return false;
        }
        if (n == 2) {
            return true;
        }
        if (n % 2 == 0) {
            return false;
        }
        for (int i = 3; i <= Math.sqrt((double) n); i += 2) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        long sum = 0;

        for (int i = 1, count = 0; count < 1000; i++) {
            if (isPrime(i)) {
                sum += i;
                count++;
            }
        }
        System.out.print(sum);
    }

}

As for the primality test I only know of these other:

for (int divisor = 2; divisor < n; divisor++) {
    if (n % divisor == 0) {
        return false;
    }
}
return true;

and

for (int divisor = 2; divisor <= n/2; divisor++) {
    if (n % divisor == 0) {
        return false;
    }
}
return true;

Answer 1

You've written a very literal and straightforward implementation to solve the challenge: test numbers for primality, and accumulate them until you have 1000 of them.

However, when you want to find many prime numbers, an algorithm such as the sieve-of-eratosthenes is more efficient than repeated trial division. Here is a benchmark that illustrates the difference. Your program follows the same basic outline as @Legato's solution, except that you haven't implemented some optimization hacks. If you just want to sum the first 1000 primes, there isn't much of a difference in execution time, but your program will not scale up as gracefully as a sieve algorithm.

Answer 2

The challenge description does not explicitly require you to check if the numbers are prime by yourself. So the most efficient way would probably be like this: 1. Store the first 1000 prime numbers in an array. 2. Sum up all elements of that array.

But that's not the goal of the challenge I guess. So here is a real improvement:

• Store Math.sqrt((double) n) in a local variable to ensure it is calculated only once per odd number.
• Start your main method with sum = 2, count = 1 and i = 3. Now you can remove if (n < 2) and if (n == 2) from your isPrime method. This saves you two checks per number.

Answer 3

Assuming you don't want to run a full sieve first, then there are a couple of improvements I can see in the isPrime() function:

First, you can combine your second and third tests into one:

if (n < 2) {
   return false;
}

if (n % 2 == 0) {
    return n == 2;
}

Second, with a little more work, you can skip multiples of 3 in your main loop by using a 2-4 wheel:

// Handle multiples of 3.
if (n % 3 == 0) {
    return n == 3;
}

// Handle multiples of 5, 7, 11, ...
int testDivisor = 5;
double limit = Math.sqrt((double) n);
int step = 2;
while (testDivisor <= limit) {
    if (n % testDivisor == 0) {
        return false;
    }

    // Step 2, 4, 2, 4 ... alternately.
    testDivisor += step;
    step = 6 - step;
}

The resulting stream of testDivisor's is prime rich, because it eliminates all even numbers and multiples of 3, like 9, 12, 15 etc. It still contains a few composites, such as 25, 35, 49, but it does reduce wasted divisions. To completely eliminate all composite numbers you need to set up a large enough sieve right at the start.

The while loop could be coded as:

for (int testDivisor = 5; testDivisor <= limit; testDivisor += step, step = 6 - step) { ... }

but I think that is less readable. YMMV.

Answer 4

Your approach needs some modifications that will improve efficiency. However, it will not matter for too few iteration (like 1000), so you will get the same results for both approaches. But if you are trying the same solution for, say, 10000 iterations, then you will get somewhat better performance.

Your code with my changes:

 import java.lang.Math;

 public class SumOfPrimes {

public static boolean isPrime(int n) {
    if (n % 2 == 0) {
        return false;
    }
    int x = (int)Math.sqrt(n);
    for (int i = 3; i <= x; i += 2) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

public static void main(String[] args) {
    long sum = 2;
   long x = System.currentTimeMillis();
    for (int i = 3, count = 1; count < 1000; i++) {
        if (isPrime(i)) {
            sum += i;
            count++;
        }
    } 
    System.out.println("Sum is "+sum);
    System.out.println("Time elapsed :"+System.currentTimeMillis()-x);
 }
}

Here I have changed the loop condition as you are calling the method each time the loop iterates. I have calculated the prime numbers starting from 3.

System.currentTimeMillis() is used to check the time elapsed for an operation. For 1000 iterations or fewer, you will not get any difference, but if you increase the value of count < 1000 to count < 100000, you will see significant changes. I checked for count < 100000 using your way and I got this output:

Sum is 62260698721
Time elapsed :581

And using the changed one, I got:

Sum is 62260698721
Time elapsed :254