list - 优化了Haskell的Eratosthenes筛

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

最佳答案

既然您说您需要此素数清单用于其他工作，所以我想您真的不需要自己实现它，对吗？您是否看过现有的现成解决方案？

现有的几个软件包提供了primes函数，该函数给出（无限）质数列表：

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

我查看了primes，arithmoi和exact-combinatorics软件包中的版本。 arithmoi中的一个似乎令人眼花blind乱。堆栈脚本：

#!/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时重新计算列表。 （请参阅文档。）