Project Euler – 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.

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.

  1. Declare an Boolean array with 2,000,000 elements (since we want to find primes less than 2 million).
  2. 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.
  3. For each value of ifrom 2 to 2000000:
    1. Visit the ith element of the array. If it is true, then:
      1. For each element (j) which is a multiple of i, change the value of array[j]to false.
      2. Add the value of i to the sum.
    2. Else, continue iterating.
  4. 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.

Solution in C++ 

Advertisements
Next Post
Leave a comment

2 Comments

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

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: