OJ's rants

It's not about you, it's about the software

Project Euler #10

| Comments

WARNING! This post contains a spoiler for Problem #10 listed at Project Euler. Do not read the rest of this post if you’re planning to attempt to solve the problem yourself.

Problem #10 takes us back into the realm of the relatively boring - prime numbers (again). The question is as follows:

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

Find the sum of all the primes below two million.

Exciting stuff! Since we’ve already got ourselves a relatively nifty prime number generator from a previous post, we can simply reuse this, along with the sum function that comes in Prelude, to generate the answer.

Here is what the code looks like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

merge :: (Ord a) => [a] -> [a] -> [a]
merge xs@(x:xt) ys@(y:yt) =
  case compare x y of
    LT -> x : (merge xt ys)
    EQ -> x : (merge xt yt)
    GT -> y : (merge xs yt)

diff :: (Ord a) => [a] -> [a] -> [a]
diff xs@(x:xt) ys@(y:yt) =
  case compare x y of
    LT -> x : (diff xt ys)
    EQ -> diff xt yt
    GT -> diff xs yt

primes, nonprimes :: [Integer]
primes    = [2, 3, 5] ++ (diff [7, 9 ..] nonprimes)
nonprimes = foldr1 f $ map g $ tail primes
  where
    f (x:xt) ys = x : (merge xt ys)
    g p         = [ n * p | n <- [p, p + 2 ..]]

main :: IO ()
main = print $ sum (takeWhile (<2000000) primes)

I don’t really have much else to say about this. I won’t bother with the performance information because it’s not really doing anything too exciting that hasn’t already been discussed.

Cheers!

Comments