"Euler #10 : Prime Summing"
by Nicolas Wu
Posted on 2 September 2010
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!