하스켈 코드를 최적화하여 2 백만 미만의 모든 소수의 합을 계산하십시오.

Question

프로젝트 오일러의 문제 10. 나는이 논의를 보았다하지만 C.

내가 계산하려면 다음 코드를 사용 :

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

그것은 계산하는 연령이 걸립니다. 나는 그것을 계산하는 더 효율적인 방법이 있는지 궁금합니다.

Answer 1

haskell에서 소수를 계산하는 많은 방법이 haskellwiki page for Prime numbers에 설명되어 있습니다. 특히 두 번째 충분히 좋은 것 같다, 그래서 당신은 이런 식을 작성할 수 있습니다

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 

솔루션이 느린 이유 위키 설명, 주요 이유 각각의 소수에 대해 하나씩 충분할 때 2000000까지 각각의 숫자에 대해 체가 설정된다는 것입니다.

Answer 2

this paper과 흥미로운 토론이 흥미 롭습니다. 결론은 sieve 구현이 에라토스테네스의 '실제'체만큼 효율적이지 않다는 것입니다.

Answer 3

나는 개인적으로 하스켈에서 본 적이 깨끗한 최적화 주요 체질 코드는 가변 벡터를 기반으로 전통 체와 오닐의 체의 형태를 모두 포함하는 NumberSieves 패키지입니다. arithmoi 패키지에있는 무시 무시하게 복잡한 코드를 사용하지 마십시오. 적어도 일부는 현재 깨져 있고 세그먼트 오류가 임의로 생성됩니다.