Оптимизировать код на Haskell, вычисляя сумму всех простых чисел ниже двух миллионов

Question

Задача 10 в проекте Эйлера. Я видел некоторое обсуждение там, но только для C.

Я использовал следующий код для расчета:

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

Требуются годы, чтобы рассчитать. Мне интересно, есть ли более эффективный способ его расчета?

Answer 1

Многие действительно быстрые способы вычисления простых чисел в haskell описаны на странице haskellwiki для простых чисел .В частности, второй кажется достаточно хорошим, так что вы можете написать это так:

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

Вы можете найти эту статью и последующую дискуссию интересной. Суть в том, что ваша реализация sieve не так эффективна, как «реальное» сито Эратосфена.

Answer 3

Самый чистый оптимизированный код простого просеивания, который я лично видел в Haskell, находится в пакете NumberSieves , который включает в себя как традиционное сито на основе изменяемых векторов, так и форму OСито ниллаНе используйте ужасно сложный код в пакете arithmoi - по крайней мере, часть его в настоящее время сломана и случайным образом вызывает ошибки сегментации.