有一个快速,功能性的素数发生器吗？

Question

假设我有一个自然数n,我想要所有素数的列表(或其他)n.

经典的主筛算法在O(n log n)时间和O(n)空间上运行- 它适用于更多命令式语言,但需要从根本上对列表和随机访问进行就地修改.

有一个涉及优先级队列的功能版本,非常漂亮 - 你可以在这里查看.这具有更好的空间复杂度O(n / log(n))(渐近更好但在实际尺度上有争议).不幸的是,时间分析是令人讨厌的,但它几乎O(n^2)(实际上,我认为它是关于O(n log(n) Li(n)),但log(n) Li(n)大约是n).

渐渐地说,使用连续的试验划分,在生成它时检查每个数字的素数实际上会更好,因为这只需要O(1)空间和O(n^{3/2})时间.有没有更好的办法？

编辑:事实证明我的计算完全不正确.文章中的算法是O(n (log n) (log log n))文章解释和证明(并参见下面的答案),而不是我上面提到的复杂的混乱.O(n log log n)如果有一个真正的算法,我仍然喜欢看到一个真正的纯粹算法.

Answer 1

这是 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)