是否有一个快速，功能的素数发生器？ [英] Is there a fast, functional prime generator?
问题描述
假设我有一个自然数 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）纯算法。
下面是Melissa O'Neill算法的Haskell实现（来自链接文章）。与Gassa关联的实现不同，我最少使用懒惰，因此性能分析很清晰 - 即在n对数日志中记录线性对数n，Eratosthenes命令Sieve的写入次数。
堆实现只是一个锦标赛树。平衡逻辑在 push ;通过每次交换孩子，我们确保对于每个分支，左子树与右子树相比相同或更大，这确保深度O（log n）。
module Sieve其中
类型Nat = Int
数据Heap = Leaf！Nat！Nat
|分支！Nat！堆！堆
派生显示
top ::堆 - > Nat
top（Leaf n _）= n
top（Branch n _ _）= n
leaf :: Nat - >堆
leaf p = Leaf（3 * p）p
分支::堆 - >堆 - >堆
分支h1 h2 =分支（min（顶部h1）（顶部h2））h1 h2
pop ::堆 - >堆
pop（Leaf np）= Leaf（n + 2 * p）p
pop（Branch _ h1 h2）
= $ b $的情况比较（顶部h1）（顶部h2） b LT - >分支（pop h1）h2
EQ - >分支（流行h1）（流行h2）
GT - >分支h1（pop h2）
push :: Nat - >堆 - >堆
push ph @（Leaf _ _）=分支（leaf p）h
push p（分支_ h1 h2）=分支（push p h2）h1
素数： ：[Nat]
素数
=让助手nh
=
LT - >的案例比较n（顶部h） n：助手（n + 2）（推n h）
EQ - >助手（n + 2）（流行h）
GT - >助手n（流行h）
2：3：助手5（叶子3）
Suppose I've got a natural number n and I want a list (or whatever) of all primes up to n.
The classic prime sieve algorithm runs in O(n log n) time and O(n) space -- it's fine for more imperative languages, but requires in-place modification to lists and random access, in a fundamental way.
There's a functional version involving priority queues, which is pretty slick -- you can check it out here. This has better space complexity at about O(n / log(n)) (asymptotically better but debatable at practical scales). Unfortunately the time analysis is nasty, but it's very nearly O(n^2) (actually, I think it's about O(n log(n) Li(n)), but log(n) Li(n) is approximately n).
Asymptotically speaking it would actually be better just to check the primality of each number as you generate it, using successive trial division, as that would take only O(1) space and O(n^{3/2}) time. Is there a better way?
Edit: it turns out my calculations were simply incorrect. The algorithm in the article is O(n (log n) (log log n)), which the articles explains and proves (and see the answer below), not the complicated mess I put above. I'd still enjoy seeing a bona-fide O(n log log n) pure algorithm if there is one out there.
Here's a Haskell implementation of Melissa O'Neill's algorithm (from the linked article). Unlike the implementation that Gassa linked to, I've made minimal use of laziness, so that the performance analysis is clear -- O(n log n log log n), i.e., linearithmic in n log log n, the number of writes made by the imperative Sieve of Eratosthenes.
The heap implementation is just a tournament tree. The balancing logic is in push; by swapping the children every time, we ensure that, for every branch, the left subtree is the same size or one bigger compared to the right subtree, which ensures depth 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)
这篇关于是否有一个快速，功能的素数发生器？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
