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.

– Project Euler Problem 10

Solution

Using our previously made Eratosthenes class for generating primes, this problem can be solved in a very easy way.

var answer = new Eratosthenes()
    .TakeWhile(x => x < 2000000)
    .Aggregate((sum, x) => sum + x)

And that was it actually. The only problem here is that it takes a bit of time. On my machine this solution takes over 2 seconds. Not very long maybe, but compared to the others that is quite a bit of time actually. Especially when I know that it could go a lot faster if I just had a faster algorithm for generating prime numbers. However, I haven't found that yet. Actually, I have, but I haven't managed to implement any of them yet... 😛

Update October, 19th 2009

Managed to finally implement another algorithm called the Sieve of Atkin. I have written about it in a different post.

Using that class, the solution to this problem looks like this:

var answer = new Atkin(2000000)
    .Aggregate((sum, x) => sum + x);

Pretty similar. But! The solution now takes only about 160 milliseconds, instead of the original 2 seconds 😄 Is that cool or what?