-- The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
-- Find the sum of all the primes below two million.

primes :: [Integer]
primes = 2:([3..] `minus` composites)
  where composites = union [multiples p | p <- primes]

multiples :: Integer -> [Integer]
multiples n = map (n*) [n..]

minus :: [Integer] -> [Integer] -> [Integer]
minus [] _ = []
minus x [] = x
minus (x:xs) (y:ys)
  | x < y  = x:(xs `minus` (y:ys))
  | x == y = xs `minus` ys
  | x > y  = (x:xs) `minus` ys
minus (_:_) (_:_) = []

union :: [[Integer]] -> [Integer]
union = foldr merge []
  where merge (x:xs) ys = x:merge' xs ys
        merge [] x = x
        merge' [] x = x
        merge' x [] = x
        merge' (x:xs) (y:ys)
          | x < y  = x:merge' xs (y:ys)
          | x == y = x:merge' xs ys
          | x > y  = y:merge' (x:xs) ys
        merge' (_:_) (_:_) = []

main :: IO ()
main = do
  putStrLn . show $ sum $ takeWhile (< 2000000) primes
