Sum of all Primes below 2000000 – Problem 10

This blog post is all about the solution to Problem 10 of Project Euler. Just like Problem 7 the problem is all about primes.  And the solution strategy I posted for problem 7 would be valid for this problem as well.

The problem reads

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

Find the sum of all the primes below two million.

There is nothing particular tricky about this question, and since there isn’t a formula for finding all primes, we will have to brute force a solution. However, the brute force solution can be more or less elegant. In the source code I have made available, you can find the solution approach from problem 7, adopted to this problem. I wont spent any more time on that method, but instead introduce you to Sieve of Eratosthenes.

Sieve of Eratosthenes

Sieve of Eratosthenes was as the name implies invented by Eratosthenes who was a Greek Mathematician living around 200 BC.

The algorithm needs to have an upper limit for the primes to find. Lets call this limit N

The algorithm works as follows.

  1. Create a list l of consecutive integers {2,3,…,N}.
  2. Select p as the first prime number in the list, p=2.
  3. Remove all multiples of p from the l.
  4. set p equal to the next integer in l which has not been removed.
  5. Repeat steps 3 and 4 until p2 > N, all the remaining numbers in the list are primes

It is a pretty simple algorithm, and the description of it on Wikipedia has a really nice graphical illustration, which I decided I couldn’t do better my self. So go and have a look at it. The algorithm finds a prime, and then marks all multiples of that primes.  The first new number will always be a prime, since all numbers which are not will have been removed.

It can be pretty straight forward to implement the algorithm, and the challenge is definitely to optimize the implementation both execution and memory wise.

I found an implementation two implementation which are similar over at Stack Overflow and digitalBush which seemed very promising. I have then further optimized it a bit. The optimized code is shown here

public int[] ESieve(int upperLimit) {
    int sieveBound = (int)(upperLimit - 1) / 2;
    int upperSqrt = ((int)Math.Sqrt(upperLimit) - 1) / 2;

    BitArray PrimeBits = new BitArray(sieveBound + 1, true);

    for (int i = 1; i <= upperSqrt; i++) {
        if (PrimeBits.Get(i)) {
            for (int j = i * 2 * (i + 1); j <= sieveBound; j += 2 * i + 1) {
                PrimeBits.Set(j, false);

    List numbers = new List((int)(upperLimit / (Math.Log(upperLimit) - 1.08366)));

    for (int i = 1; i <= sieveBound; i++) {
        if (PrimeBits.Get(i)) {
            numbers.Add(2 * i + 1);

    return numbers.ToArray();

Once we have a list of all the primes we need the rest of the code is a trivial for loop summing up the array. You can check the source code for that bit. In the following sections I will touch on different aspects of the code.

Data representation

It uses a BitArray to store all the numbers. It is a enumerable type which uses one bit per boolean. Using a BitArray means the algorithm will limit the memory usage by a factor 32 compared to an array of booleans according this discussion. However, it will lower the operational performance. We need an array to hold 2.000.000 numbers, which means a difference of 250kB vs. 8MB.

I played around with it a bit, and didn’t see much of a performance difference for a small set of primes. For a large set of primes I noticed that the BitArray was slightly faster. This is likely due to better cache optimization, since the the BitArray is easier to store in the CPU cache, and thus increasing the performance.

Eliminating even numbers

Over at digitalBush he optimizes his code by skipping the even numbers in the loops. I have chosen a bit of another approach, to avoid allocating memory for it. It just takes a bit of keeping track of my indexes.

Basically I want to  start with three and then for a counter i = {1,2,….,N/2} represent every odd number p = {3,5,7,….,N}. That can be done as p = 2i+1. And that is what I have done in the code. It makes the code a bit more complex, but saves half the memory, and thus it can treat even larger sets.

Furthermore we start our inner loop at p2 = (2i+1)(2i+1) = 4i2 + 4i + 1, which will have the index 2i(i+1), which is where we start the search of the inner loop. By increasing p=2i+1 indexes in every iteration of the inner loop, I am jumping 2p, and thus only taking the odd multiples of p. Since multiplying with an even number will give an even result, and therefore not a prime.

Sieve of Atkin

Another Sieve method to generate primes is the Sieve of Atkin. It should be faster than the Sieve of Eratosthenes. I have made a reference implementation of it, but I can’t wrap my head around how to optimize it, so I have never been able to optimize it to the same degree as the Sieve of Eratosthenes. However, I have included the reference implementation in the source code, so you can play around with it if you like.

Wrapping up

This post took a bit of a different approach. I have worked hard to really optimize the code. Since I believe that the Sieve method for finding primes will be used later. So making a reusable bit of fast code, will make later problems easier to solve.

I took three 3 different approaches and tried to optimize them.  The result of the three are

Prime sum of all primes below 2000000 is 142913828922
Solution took 203,125 ms using Trial Division
Prime sum of all primes below 2000000 is 142913828922
Solution took 31,25 ms using Sieve of Eratosthenes
Prime sum of all primes below 2000000 is 142913828922
Solution took 31,25 ms using Sieve of Atkin

The difference between the two sieve methods are not really noticeable for such small numbers, but if we start calculating all primes below one billion, the differences in execution time will show. And as usual you can download the source code.

If you can come up with further optimizations of the sieve methods, I would appreciate you to leave a comment.  I am always eager to learn more and speeding things up further.

Posted by Kristian in Project Euler, 31 comments

A 1000 Pythagorean triplets – Problem 9

Today’s problem in Project Euler, is related to probably THE most well known theorem of all times.  Pythagoras theorem stating that Geometric interpretation of Pythagoras

The square of the hypotenuse is the sum of squares of the two other sides.

It can also be stated in a more geometrical way as

In any right triangle, the area of the square whose side is the hypotenuse (the side opposite the right angle) is equal to the sum of the areas of the squares whose sides are the two legs (the two sides that meet at a right angle

Which can also be shown in a graphical sense, on the figure to the right, where the blue area equals the orange area.

But enough with the background info, the problem reads

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

a2 + b2 = c2

For example, 32 + 42 = 9 + 16 = 25 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.

Find the product abc.

Continue reading →

Posted by Kristian in Project Euler, 36 comments

Solution to Problem 8 of Project Euler

We have now treated a couple of problems where a really clever solution could be derived from different branches of number theory. Problem 8 of Project Euler is inherently different.  The problem goes

Find the greatest product of five consecutive digits in the 1000-digit number.



Continue reading →

Posted by Kristian in Project Euler, 24 comments

Project Euler – Problem 7

Now we reached Problem 7 of Project Euler which is about prime numbers. The problem reads

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

We could solve this by brute force checking all the numbers, or we could reuse part of the solution to problem 5, where we generated a list of primes using trial division with already found prime numbers. I haven’t found a way to solve this without finding the 10000 primes before finding the answer.

Wikipedia comes with a great article about prime numbers, which also refers to several methods for checking if a number is a prime. We will take a bit of simpler approach though. But dive into the article, it is pretty interesting.

Continue reading →

Posted by Kristian in Project Euler, 7 comments

Project Euler – Problem 6

This exercise has a longer problem description than the previous, so lets jump right into it.

The sum of the squares of the first ten natural numbers is,

12 + 22 + … + 102 = 385
The square of the sum of the first ten natural numbers is,

(1 + 2 + … + 10)2 = 552 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 – 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Continue reading →

Posted by Kristian in Project Euler, 8 comments

Project Euler – Problem 5

Lets jump right into solving Problem 5 of Project Euler and let me try to give you an answer on how to solve it. The problem formulation is :

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible (divisible with no remainder) by all of the numbers from 1 to 20?

Once again I will provide you with two different solutions and some tips and tricks on how to speed them up a bit.
Continue reading →

Posted by Kristian in Project Euler, 32 comments

Project Euler – Problem 4

Today it is time to look at the solution to Problem 4 of Project Euler. It differs a bit in the nature of the problem from the first 3 we have looked at so far. However, it is still mathematics and a solution can still be coded, and most important it is still fun.

The problem formulation reads:

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 * 99.

Find the largest palindrome made from the product of two 3-digit numbers.

I think it is a nice recreational little exercise.

Continue reading →

Posted by Kristian in Project Euler, 28 comments

Project Euler – Problem 3

I am sorry, I haven’t posted anything for a while. I have been busy moving, and is currently without an Internet connection. However I couldn’t keep away any more.

Problem 3 in Project Euler reads:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

I used two different approaches for this, and lets get right to them. Continue reading →

Posted by Kristian in Project Euler, 22 comments

Project Euler – Problem 2

The problem description of Problem 2 of Project Euler reads

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

Before heading on with a solution, I will make a small comment on the problem formulation. Usually the first two numbers in the Fibonacci sequence is defined as F1 = F2 = 1. But that is just nitpicking and wont change anything in the solution.

Continue reading →

Posted by Kristian in Project Euler, 27 comments

Project Euler – Problem 1

Now that the fluff around the coding is covered, we are ready to solve the first problem.

The description of problem 1 on Project Euler reads

Find the sum of all the multiples of 3 or 5 below 1000.

There are multiple methods for finding the solution for this problem…
Continue reading →

Posted by Kristian in Project Euler, 47 comments
This site uses cookies.