Problem 010 : Summation of Primes

Summation of primes

Problem 10

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

                                                                                                         https://projecteuler.net/problem=10

Problem 10 is about primality of integers.

There are two main ways to do this, but let's start with the one we already know.

First method is to use boolean isPrime(int n) to check each integer until we reach two million.

public static boolean isPrime(int n)
{
     if (n <= 3) return n > 1;
     else if (n % 2 == 0 || n % 3 == 0) return false;
     else
     {
      for (int i = 5, end = (int)Math.sqrt(n); i <= end; i += 6)
      {
       if (n % i == 0 || n % (i + 2) == 0) return false;
      }
     }
     return true;
}

Loop through each integer using for-loop and check their primality.

We get the answer in 603 ms. Pretty decent, but we are not really satisfied.


So here comes our new approach to this problem.

But before that, let's briefly talk about different ways to store integers in an array.

We will consider storing 1, 3, 5, 8 into an array.


First way is to directly store integers in an array.

index	0	1	2	3
value	1	3	5	8

Second way is to have a boolean array and stored number has true value in its index.

index	0	1	2	3	4	5	6	7	8
value	false	true	false	true	false	true	false	false	true

This array contains exactly same information as the first array.

Only index 1, 3, 5, 8 have true value, which means the "if array has that value" will be true.

The only difference is that the array size is usually larger than the number of integers we want to store.

However, it is phenomenally faster for finding certain integers in the array and adding/ removing certain integer.

Adding would be just changing that index to true, removing would be false.



Using this basic idea, we will now use the Sieve of Eratosthenes.

Sieve of Eratosthenes uses exactly same concept as the second example.

We will make a boolean array called isPrime, and isPrime[n] will return whether n is a prime or not.


The basic concept of the sieve is that "any multiple of prime number is not a prime."

Let's start with a table of numbers from 1 to 20.

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20

Now, by definition, 1 is not a prime. (as well as any integer less than or equal to 0)

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20

We are on 2 right now. We started with 0, and until we came to 2, no number could cross out 2.

Therefore 2 is a prime number.

Because 2 is a prime number, any multiple of it (which will be rest of even integers) won't be prime.

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20

Now, we are on 3. Until we came to 3, no number could cross out 3.

Therefore 3 is a prime number.

Because 3 is a prime number, any multiple of it (6, 9, 12, 15, ...) won't be prime.

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20

Now we are on 4. Uh-oh, it's already crossed out. Until we came to 4, some number crossed out 4.

So 4 is not a prime, and we just go on to the next number.


We are on 5. Until we came to 5, no number could cross out 5.

Therefore 5 is a prime number.

Because 5 is a prime number, any multiple of it (5, 10, 15, ...) won't be prime.

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20

And we notice that no additional composite numbers were crossed out this time.

So we know our limit for checking the prime is up to the square root of the original limit.

For example, square root of 20 is 4.47, and 5 is above that limit, so we didn't need to check 5.

In other sieves, we will repeat the above process until we get to the square root of original limit.

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20

Notice that the uncrossed numbers are all prime numbers.

So if we convert this table into an array of boolean values,

the crossed-out index will have false value, while survived index will have true value.

And this information will be stored in isPrime array and we can just call array every time we need.

For example, if we want to check whether 9 is a prime number, then:

public static void main(String[] args)
{
    if (isPrime[9])
    {
        System.out.println("9 is a prime number.");
    }
    else System.out.println("9 is not a prime number."); // this will print
}

And here is the implementation for the sieve.

public static boolean[] primeList(int n)
{
        //sieve of Eratosthenes
        boolean[] prime = new boolean[n+1];
        Arrays.fill(prime, 2, prime.length, true);
        for (int i=4; i < prime.length; i+=2) prime[i] = false;
        for (int i=3, end = (int)Math.sqrt(n); i <= end; i+=2)
        {
         if (prime[i])
          for (int j=i*i; j <= n; j+=2*i)
           prime[j] = false;
        }
        return prime;
}

Answer is 142913828922
Execution time is 15 ms, or 0.015 seconds
Source code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem010.java