algorithm - 是否有快速、实用的素数生成器？

Question

假设我有一个自然数 n，并且我想要一个包含 n 以内的所有素数的列表(或其他任何内容)。

经典的素数筛算法在 O(n log n) 时间和 O(n) 空间内运行——它适用于更多命令式语言，但需要 in-以基本的方式对列表和随机访问进行修改。

有一个涉及优先级队列的功能版本，非常漂亮——你可以看看here .这在大约 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)