假设我有一个自然数n我想要一个包含所有素数的列表（或其他）n.
经典的素筛算法运行在O(n log n)时间和O(n)空间——对于命令式语言来说这很好，但需要从根本上对列表和随机访问进行就地修改。
有一个涉及优先级队列的功能版本，非常灵活 - 你可以查看一下here https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf。这具有更好的空间复杂度，约为O(n / log(n))（渐近更好，但在实际规模上有争议）。不幸的是，时间分析很糟糕，但已经很接近了O(n^2)（其实我觉得是关于O(n log(n) Li(n)), but log(n) Li(n)大约是n).
渐近地讲，实际上最好在生成每个数字时使用连续的试除法来检查它的素数，因为这只需要O(1)空间和O(n^{3/2})时间。有没有更好的办法？
Edit:事实证明我的计算完全错误。文章中的算法是O(n (log n) (log log n))，文章对此进行了解释和证明（并参见下面的答案），而不是我上面提出的复杂混乱。我仍然很高兴看到真正的O(n log log n)纯粹的算法（如果有的话）。
这是 Melissa O'Neill 算法的 Haskell 实现（来自链接的文章）。与 Gassa 链接的实现不同，我最大限度地减少了惰性，因此性能分析很清晰 -O(n log n log log n)，即 n log log n 中的线性对数，即命令式埃拉托色尼筛法进行的写入次数。
堆实现只是一个锦标赛树。平衡逻辑是push;通过每次交换子树，我们确保对于每个分支，左子树的大小相同或比右子树大一，这确保了深度 O(log n)。
module Sieve where
type Nat = Int
data Heap = Leaf !Nat !Nat
| Branch !Nat !Heap !Heap
deriving Show
top :: Heap -> Nat
top (Leaf n _) = n
top (Branch n _ _) = n
leaf :: Nat -> Heap
leaf p = Leaf (3 * p) p
branch :: Heap -> Heap -> Heap
branch h1 h2 = Branch (min (top h1) (top h2)) h1 h2
pop :: Heap -> Heap
pop (Leaf n p) = Leaf (n + 2 * p) p
pop (Branch _ h1 h2)
= case compare (top h1) (top h2) of
LT -> branch (pop h1) h2
EQ -> branch (pop h1) (pop h2)
GT -> branch h1 (pop h2)
push :: Nat -> Heap -> Heap
push p h@(Leaf _ _) = branch (leaf p) h
push p (Branch _ h1 h2) = branch (push p h2) h1
primes :: [Nat]
primes
= let helper n h
= case compare n (top h) of
LT -> n : helper (n + 2) (push n h)
EQ -> helper (n + 2) (pop h)
GT -> helper n (pop h)
in 2 : 3 : helper 5 (leaf 3)
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
