Project Euler #10 - sum of primes below two million

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.


Find the sum of all the primes below two million.

public class Java {

public static void main(String[] args) {
    long start = System.nanoTime();

    long sum = 0;

    for (int i = 2; i < 2000000; i++) {
        boolean isPrime = true;

        if ((i % 2 == 0 || i % 3 == 0) && (i!=2 || i!=3 || i!=5)) {
            isPrime = false;
        } else {
            for (int j = 5; j <= Math.sqrt(i); j = j + 6) {
                if (i % j == 0 || i % (j + 2) == 0) {
                    isPrime = false;
                    break;
                }
            }
        }

        if (isPrime == true) {
            sum += i;
        }
    }

    System.out.println(sum);
    long end = System.nanoTime();
    System.out.println(end - start);
}

This is probably not efficient since i am using a lot of if-else statements and conditions.

Well, first of all, sorry, but your code is buggy. You are missing 2 and 3, because of this:

if ((i % 2 == 0 || i % 3 == 0)

...since this will be true for 2 and 3. So your result is off by 5.

Also this part is 100% useless:

(i!=2 || i!=3 || i!=5))

How many values for i you can imagine for which this statement is false?

• Let's try i = 1 -> true, because 1 != 2 (i != 2)

• Now we try i = 2 -> true, because 2 != 3 (i != 3)

• Now we try i = 3 -> true, because 3 != 2 (i != 2)

• Last try: i = 5 -> true, because 5 != 2 (i != 2)

So, this statement is always true.

Anyway, another solution (getting more speed by sacrificing memory) would be to not calculate if every number is a prime, but do something like this...

final int limit = 2000 * 1000;

final boolean[] knownNotPrime = new boolean[limit + 1];

long sum = 0;

for (int i = 2; i < limit; i++) {

    if (!knownNotPrime[i]) {
        sum += i;

        for (int j = 2; j <= (limit / i); j++) {
            knownNotPrime[j * i] = true;
        }
    }

}

In other words, for every prime you calculate the multiples (up to the limit) and store them in a boolean array (you could decrease the memory by a factor of 8 by using a bitfield, just didn't want to complicate the whole thing).

Since "being not a multiple of any number lesser than itself" is pretty much the definition of "prime", you already know if a number is a prime when you reach it and it's not marked in the array. And if it isn't, you know that it's a multiple of some lesser prime - and thus, all it's multiples will already be known as non-prime, no need to re-calculate them.

Your code takes around 217ms to run, mine takes 17, but on the other hand, mine takes way more than 12 times the memory, even if you used a bitfield.

Note: After using google and trying to remember what I learned in school, this is probably a variation of the Sieve of Eratosthenes and I have no idea how good this implementation is. Probably there are much better solutions out there, I guess.

StackExchange Code Review Q#102051, answer score: 4