Project Euler #10 in Java

Question

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.

My solution:

public class PrimeSumFinder {

    private static final int MAX = 2_000_000;

    public static void main(String[] args) {
        long time = System.nanoTime();
        long result = getSumOfPrimesBelowN(MAX);
        time = System.nanoTime() - time;
        System.out.println("Result: " + result
                + "\nTime used to calculate in nanoseconds: " + time);
    }

    private static long getSumOfPrimesBelowN(int n) {
        boolean[] isPrimeArray = new boolean[n + 1];
        for (int i = 2; i <= n; i++) {
            isPrimeArray[i] = true;
        }
        for (int i = 2; i * i <= n; i++) {
            if (isPrimeArray[i]) {
                for (int j = i; i * j <= n; j++) {
                    isPrimeArray[i * j] = false;
                }
            }
        }
        // Sum the primes
        int index = 0;
        long result = 0;
        for(boolean isPrime : isPrimeArray) {
            if(isPrime) {
                result += index;
            }
            index++;
        }
        return result;
    }

}

Output:

Result: 142913828922
Time used to calculate in nanoseconds: 87694113

Questions:

1. Is this the most efficient way? If not, what is a better way?
2. Does it have bad practices in it?

Answer 1

For your inner for-loop you have

for (int j = i; i * j <= n; j++) {
                isPrimeArray[i * j] = false;
            }

Once you find a prime number, you can start knocking out factors at i*i, since any multiple of i less than that would be a multiple by an existing smaller prime you already ran elimination on in a previous iteration!

Also, you have to go through the entire array, so your ending point would be j<=n

And lastly, you are iterating over multiples of i! So your loop can increment at j+=i at each step. Leaving the final fixed loop to be:

for (int j = i*i; j < n; j+=i) {
                isPrimeArray[j] = false;
            }

This should cut down on plenty of iterations.

Also you may want to consider breaking your outer loop into two for-loops. First a for loop for multiples of 2

for(int i = 4; i < n; i+=2) //set to false

Since 2 is the only even prime, this means that in your main code (your old outer loop) can be rewritten to only go over odd numbers, cutting down half the iterations!

Another time saving tip is to also process your loop up to Math.sqrt(n) because once you hit the square root, anything after that is prime because multiples of those numbers fall outside of your sieve.

int limit = (int)Math.sqrt(n) + 1
for(int i = 3; i < limit ; i+=2) //inner loop revised above

So now you are not only skipping even numbers, but also only going up to the square root of n, rather than n itself.

Other than that your spacing and naming seems to be fine. Though I would recommend you separate the tasks out into different methods. Namely split your function into a generateSieve() function that makes the sieve, and then a sumOfPrimes function that takes the sieve as a parameter and outputs the sum.

I say this because the sieve itself is a widely used technique for Project Euler problems, and you won't just want to find the sum! So I recommend making generateSieve() (or whatever you may name it) it's own function.