Efficient Sum of Primes

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;


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 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.

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.
• In addition to your last point: If you change i++ in the loop to i += 2, you can also drop the if (n % 2 == 0). Jun 10, 2015 at 13:37
• I don't like the idea of making isPrime wrong because it knows the assumptions that main makes. If you've removed those initial checks because the main method doesn't require them, then isPrime(1) will return true when somebody else calls it later, and that's just not right. The preconditions need to stay in isPrime. Jun 10, 2015 at 20:06
• @MillieSmith: In general you are right of course. In this case I think it is a valid improvement because nobody will use his method and the task was to find prime numbers fast. In my opinion it is valid to create a method that has a specific contract. The method should have a comment informing the clients about the usage. Jun 11, 2015 at 8:26

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.

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.

 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

• I don't see how this is reviewing the code -- to me, it looks more like you gave your own solution.
– Nic
Jun 10, 2015 at 16:12
• @QPaysTaxes : i have not given my solution!! i have changed few things in question only which should be there to improve performance Jun 10, 2015 at 18:01
• Then explain how you changed it, rather than saying "i changed your code as : [sic]" and dumping the modified code.
– Nic
Jun 10, 2015 at 19:05
• Your code is wrong, actually. I just tested it (See here) and it says that 2 isn't prime. You'll need to add back the == 2 check.
– Nic
Jun 10, 2015 at 20:43
• Anyway, let's forget about the bug in your code -- it won't even compile. Go ahead, try it. Copy/paste your badly-indented, buggy code into your favorite editor and try to compile. It won't.
– Nic
Jun 11, 2015 at 21:16