Optimize Haskell code calculating the sum of all the primes below two million
haskell, optimization, primes
Solution
Many really fast ways of calculating prime numbers in haskell is described on the haskellwiki page for Prime numbers. Specifically the second one seems to be good enough, so you might write it like this:
main = print . sum . takeWhile (< 2000000) $ primes
primes = 2: 3: sieve (tail primes) [5,7..]
sieve (p:ps) xs = h ++ sieve ps [x | x <- t, rem x p /= 0]
where (h,~(_:t)) = span (< p*p) xs
Running it we get:
ghc --make -O2 Euler10.hs
time ./SOAns
142913828922
real 0m1.598s
user 0m1.577s
sys 0m0.017s
The wiki describes why your solution is so slow, the main reason is that a sieve is set up for each number up to 2000000, when one for each prime is sufficient.
Problem
Problem 10 in Project Euler. I saw some discussion there but only for C. I used the following code to calculate: ``` print . sum . sieve $ [2..2000000] where sieve [] = [] sieve (x:xs) = x : sieve (filter ((/= 0) . (`mod` x)) xs) ``` It takes ages to calculate. I am wondering if there is any more efficient way to calculate it?