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

Find the sum of all the primes below two million.

Problem 10 is reasonably demanding. Unless you are familiar with Eratosthenes Sieve method (or any other sieve method), solving this problem in less than a minute will be next to impossible.

## Sieve of Eratosthenes

In mathematics, the **sieve of Eratosthenes** , one of a number of prime number sieves, is a simple, ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking as composite (i.e. not prime) the multiples of each prime, starting with the multiples of 2.

Wikipedia Entry

## General Algorithm

Above is a visual representation of the algorithm. Now, we must translate it into program code, in order to solve the problem.

- Declare an Boolean array with 2,000,000 elements (since we want to find primes less than 2 million).
- Fill the entire array with ‘true’ or 1. By doing this, we are assuming that all the numbers are prime. We will now “cross out” (mark false) those numbers which are multiples of other numbers.
- For each value of
*i*from 2 to 2000000:- Visit the
*i*th element of the array. If it is true, then:- For each element (
*j*) which is a multiple of*i,*change the value of

to false.**array[j]** - Add the value of
*i*to the sum.

- For each element (
- Else, continue iterating.

- Visit the
- Print the sum.

On my machine, the program takes about 0.063 seconds to run. It’s slightly memory intensive, requiring an array of 2000000 bytes to be allocated, but it can’t be helped.

If you know of some other prime number sieve which works faster, do let me know.

## ouija board

/ February 3, 2012i love your blog, i have it in my rss reader and always like new things coming up from it.

## virajmahesh

/ February 20, 2012Thanks 🙂