Оптимизированное сито эратосфена в Хаскеле - PullRequest
Новая
       46

Оптимизированное сито эратосфена в Хаскеле

0 голосов
/ 09 февраля 2019

Я новичок в Haskell и для чего-то, что я реализую, мне нужен список простых чисел.Я пытался написать один, но он слишком медленный.

Это то, что я пытался сделать. 

primeList = primes 1000
primes :: Int -> [Bool]
primes x = primeRecursion 2 ([False,False] ++ replicate (x-1) True)
    where primeRecursion y l
            | y == x = l
            | not (l!!y) = primeRecursion (y+1) l
            | otherwise = primeRecursion (y+1) [ if (a>y && (a `mod` y == 0)) then False else l!!a | a <- [0..x]]

Это работает, но алгоритмическая сложность выше, чем процедурный эквивалент, так как дляКаждое простое число проходит через весь список, а не только его кратные.Я не могу найти способ сделать это O (n (log n) (log log n)), потому что работает функциональное программирование.Что такое (желательно простой и понятный) способ сделать это?

1 Ответ

0 голосов
/ 25 марта 2019

Поскольку вы говорите, что вам нужен этот список простых чисел для еще , что вы делаете, я думаю, вам не нужно реализовывать его самостоятельно, не так ли?Вы смотрели на существующие готовые решения?

Несколько существующих пакетов предоставляют функцию primes, которая дает (бесконечный) список простых чисел: 

primes :: [Integer]  -- or some other integral type
primes = [2,3,5,7,11,13,...]

Я смотрел наверсии в пакетах primes, arithmoi и exact-combinatorics.Тот, что в arithmoi кажется ослепительно быстрым.Сценарий стека: 

#!/usr/bin/env stack
-- stack --resolver lts-12.21 script --optimize
import Math.NumberTheory.Primes (primes)

main :: IO ()
main = print (sum $ take 1000000 primes)

использует arithmoi-0.7.0.0 и суммирует первые десять миллионов простых чисел примерно за секунду.

Если вы используете более новую версию пакета в arithmoi-0.8.0.0, тогда primesбыл переопределен как полиморфный список, поэтому вы захотите определить мономорфную копию нужного целочисленного типа: 

primes' :: [Integer]
primes' = primes

и использовать ее, чтобы избежать повторного вычисления списка каждый раз, когда используется primes,(См. Документацию.)

...