In this blog post we will be looking at problem 10 of Project Euler and we will program a solution in Java.

The problem of Project Euler found here, below is the problem for quick lookup.

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

Find the sum of all the primes below two million.

-Project Euler problem 10

What we need is a way to find out if a number is a prime number. A prime number is a whole number only divisible by itself or one without leaving a remainder after the dot/comma.

The fastest way to generate prime numbers is to use the Sieve of Eratosthenes algorithm. This has a limitation that you need a maximum number to check up to. But let’s first brute force it which is a lot slower in computational time but a lot easier to grasp.

long sum = 2;
for (int i = 3; i < 2_000_000; i += 2) {
    if (isPrime(i)) { //function discussed below
        sum += i;
    }

}
System.out.println(sum);

We start by creating a variable to hold the sum. We initialize the value to two(first prime). We need to make it a long because an integer is to small which leads to looping over into negatives since the numbers an int can hold is -2,147,483,648 to 2,147,483,647. A long can hold number from -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807.

Then we declare a loop with a max of two million, we start the loop counter at three since we initialized the sum to two, we need to consider the next number as prime which is three. We add two to the loop counter(i) every loop since only uneven numbers can be prime so we do not consider even numbers at all.

Then we check in the if statement if it is a prime using a function if it is a prime we add it to the sum.

isPrime

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

This function takes as argument a number to check for being a prime. We set the loop counter used in the while to two which is the first prime. The while loop condition loops from two to the square root of the input. If at any point the division results in zero this means the argument number is not a prime and we return false and exit the function. If after trying every single number from two to the square root of the input argument number all result in a remainder we return true since the argument number is a prime.

Sieve of Eratosthenes method

int max = 2_000_000;
boolean[] markings = new boolean[max];
for (int i = 2; i <= Math.sqrt(max); i++) {
    if (markings[i] == false) {
        int original = i;
        for (int j = i + i; j < max; j = j + original) {
            markings[j] = true;
        }
    }
}

long sum = 2;
for (int i = 3; i < max; i += 2) {
    if (markings[i] == false) {
        sum += i;
    }
}
System.out.println(sum);

This is the quickest method I have found which takes about 20ms on my machine with a max of 2_000_000. We start by declaring the max of the numbers to consider as prime(this method does not work without a max). We loop from two to the square root of the max incrementing by one. If the current Boolean in the array is false(thus is a prime) we mark all multiples of the number(variable i) as not a prime by setting the Boolean to true.

After looping through all the entries this leaves us with just the primes(false in the boolean array) which we can then add in the last for loop and print to get the answer.

Check out the ‘Project Euler in Java’ page for more solutions!

Link to github.

That was Project Euler problem 10 in Java!