Project Euler - Problem 10

Welcome to week 10 of my Project Euler series.

Problem 10:

Calculate the sum of all the primes below two million.

Details:

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

Find the sum of all the primes below two million.

Code:

// Calculate the sum of all the primes below two million.

class Project0010

{

static void Main(string[] args)

{

var numbers = SieveEratosthenes(2000000);

long total = 0;

foreach (var num in numbers)

total += num;

Console.Write(total);

Console.Read();

}

// Sieve of Eratosthenes

public static int[] SieveEratosthenes(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)));

numbers.Add(2);

for (int i = 1; i <= sieveBound; i++)

{

if (PrimeBits.Get(i))

{

numbers.Add(2 * i + 1);

}

}

return numbers.ToArray();

}

}

Solution:

This one certainly had me thinking and even doing a bit of research.  It is possible to brute force your way through it, but the problem is that Project Euler explicitly states that each problem can be solved by a moderate computer in under a minute. After the brute force route had run for about 5 minutes I decided that another approach was needed.  Since it has been a while since I had a math course I hit the web and did some searching.  I checked into different algorithms for working with primes and particularly with the sum of primes. One name that kept popping up was "Sieve of Eratosthenes."  

Wikipedia describes the Sieve so - "In mathematics, the Sieve of Eratosthenes (Greek: κόσκινον Ἐρατοσθένους) is a simple, ancient algorithm for finding all prime numbers up to a specified integer. It works efficiently for the smaller primes (below 10 million)." It goes on to give a great description of how it works with a nice animation to really help drive the point home.  The general idea behind it is that if 2 is a prime, then all multiples of 2 can not be.  By eliminating all of those from the list of numbers that is being searched the field narrows itself relatively quickly.  This is done until you reach the square root of the number that you are looking for.  Once you get past the Square Root of the maximum number that you are looking for then it is safe to assume that all the primes have been found.  This is more of an optimization step, but it is still one that can be taken if you want.  It can even be taken one step further by starting the elimination of numbers with the square of the prime that you found, since it has been proven that all numbers between the prime you found and it's square should already be crossed out by process of elimination.  It really is quite the interesting piece of mathematical info to have.

I have recreated this by first creating an array with the number of elements being equal to the number that I am searching to. It is a BitArray to minimize the overhead and speed up the whole process. I go through this list to decide if a number is prime or not (true or false).  At the end I translate this list from simple set or not set values to actual numbers.  Send this back as a return value and some addition later I have my answer.

Just as a side note, it is possible to start your Sieve with the number three and then bump up your iterator by two each pass to improve the performance even more.  This is possible because the first round of eliminations will automatically knock out each even number so there is no need to even check them.

Enjoy!