优化Haskell代码，计算所有素数之和低于200万 [英] Optimize Haskell code calculating the sum of all the primes below two million

问题描述

Project Euler中的问题10。我看到了一些讨论，但只有C。

我使用下面的代码来计算：

 打印。总和。筛$ $ [2..2000000]其中
 sieve [] = [] 
 sieve（x：xs）= x：sieve（filter（（/ = 0）。（`mod` x））xs ）
  

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

解决方案

许多真正快速计算haskell中的素数的方法是请参阅 Prime数字的haskellwiki页面。具体来说，第二个似乎是够好的，所以你可以这样写：

  main = print。总和。 takeWhile（<2000000）$ primes 
 
 primes = 2：3：sieve（tail primes）[5,7 ..] 
 
 sieve（p：ps）xs = h ++ sieve ps [x |其中（h，〜（_：t））= span（< p * p）xs 
  pre> 
 
 
运行它我们得到： 
 
 
  ghc --make  - O2 Euler10.hs 
 time ./SOAns 
 142913828922 
 
 real 0m1.598s 
 user 0m1.577s 
 sys 0m0.017s 
  
这个wiki描述了为什么你的解决方案如此之慢，主要原因是每个数字设置了一个筛号高达2000000 ，当每个素数都足够时。 
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?
解决方案
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.

                        
这篇关于优化Haskell代码，计算所有素数之和低于200万的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！