Euler #10 : Prime Summing

by Nicolas Wu

Posted on 2 September 2010

Tags: Haskell, Euler

The task for this week’s Project Euler problem is as follows:

Calculate the sum of all the primes below two million.

Well, we’ve already seen how to generate primes, and here we’ll be using the spanPrimes definition from Euler #7:

primes :: [Int]
primes = 2 : 3 : sieve 0 (tail primes) 5
 where
  sieve k (p:ps) x = [n | n <- [x,x+2..p*p-2]
                        , and [n`rem`p/=0 | p <- fs]]
                     ++ sieve (k+1) ps (p*p+2)
   where fs = take k (tail primes)

Now we need to be able to sum all the values from this list that are less than two million.

We’ve already seen a summing problem where a predicate is involved in Euler #2, where we used a takeWhile to take all the values that satisfied a condition. Here we’ll be using this function again, to make sure that our values are all below two million, before summing the result:

euler10 = sum $ takeWhile (< 2000000) primes

Summary

This week’s problem was pretty easy to solve, since we used functions we had already been introduced to.

• Reusing functions makes quick work of related problems.

As of next week I’ll be shelving the Project Euler series of posts for a while, and moving onto something completely different. I hope you’ve enjoyed the ride!

Comments