list - Haskell 中优化的 Eratosthenes 筛

Question

我是 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)) 的方法。这样做的(最好是简单明了的)方法是什么？

Answer 1

既然你说你需要这个素数列表来做某事否则 你正在做，我想你真的不需要自己实现它，是吗？您是否查看过现有的现成解决方案？

几个现有的软件包提供了 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用来。 (请参阅文档。)