Optimiser le code Haskell en calculant la somme de tous les nombres premiers inférieurs à deux millions

Question

Problème 10 dans le projet Euler. J'y ai vu une discussion, mais seulement pour C.

je le code suivant pour calculer:

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

Il faut calculer les âges à. Je me demande s'il existe un moyen plus efficace de le calculer?

Answer 1

De nombreux moyens très rapides de calculer les nombres premiers en haskell sont décrits sur le haskellwiki page for Prime numbers. Plus précisément, le second semble être assez bon, alors vous pourriez écrire comme ceci:

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 

Son exécution, nous obtenons:

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

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

Le wiki décrit pourquoi votre solution est si lent, la raison principale est qu'un tamis est mis en place pour chaque nombre jusqu'à 2000000, quand un pour chaque premier est suffisant.

Answer 2

Vous pouvez trouver this paper et la discussion qui s'ensuit intéressante. L'essentiel est que votre implémentation sieve n'est pas aussi efficace que le véritable tamis d'Eratosthène.

Answer 3

Le propre optimisé premier code tamiser J'ai personnellement vu dans Haskell est dans le paquet NumberSieves, qui comprend à la fois un tamis traditionnelle à base de vecteurs mutables et une forme de tamis de O'Neill. N'utilisez pas le code horriblement complexe dans le package arithmoi: au moins une partie de ce code est actuellement interrompue et produit de manière aléatoire des erreurs de segmentation.