优化Haskell代码,计算低于200万的所有素数之和

Question

Euler项目中的问题10.我在那里看到了一些讨论但只针对C.

我使用以下代码来计算:

print . sum . sieve $ [2..2000000] where
    sieve [] = []
    sieve (x:xs) = x : sieve (filter ((/= 0) . (`mod` x)) xs)

计算需要很长时间.我想知道是否有更有效的方法来计算它？

Answer 1

在haskellwiki页面上描述了许多真正快速计算haskell素数的方法.特别是第二个似乎足够好,所以你可能这样写:

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 

运行它我们得到:

ghc --make -O2 Euler10.hs
time ./SOAns
142913828922

real    0m1.598s
user    0m1.577s
sys 0m0.017s

维基描述了为什么你的解决方案如此缓慢,主要原因是为每个数字设置了一个筛子,最高可达200​​0000,当每个数量的一个就足够了.

Answer 2

您可能会发现本文和随后的讨论很有趣.最重要的是,你的sieve实施不如Eratosthenes的"真实"筛选效率高.