algorithm - The Genuine Sieve of Eratosthenes——用于生成素数的算法

Question

今天我看了一篇论文:

O'Neill, Melissa E., "The Genuine Sieve of Eratosthenes", Journal of Functional Programming, Published online by Cambridge University Press 09 Oct 2008 doi:10.1017/S0956796808007004.

描述了一种使用优先队列产生素数的算法:

sieve [] = []
sieve (x:xs) = x : sieve' xs (insertprime x xs PQ.empty)
    where
        insertprime p xs table = PQ.insert (p*p) (map (* p) xs) table
        sieve' [] table = []
        sieve' (x:xs) table
            | nextComposite <= x = sieve' xs (adjust table)
            | otherwise = x : sieve' xs (insertprime x xs table)
            where
                nextComposite = PQ.minKey table
                adjust table
                    | n <= x = adjust (PQ.deleteMinAndInsert n' ns table)
                    | otherwise = table
                    where
                        (n, n':ns) = PQ.minKeyValue table

primes = sieve [2 .. ]

算法乍一看好像是对的，但是有一点没看懂:

它使用的 PQ 如何处理重复的最小优先级？

我手工做了一些模拟，我发现这可能会导致错误。

如果有人能解释一下，我将不胜感激!

Answer 1

论文是这样描述正在使用的优先级队列的:

Given these needs, a priority queue is an attractive choice, especially since this data structure natively supports multiple items with the same priority (dequeuing in them arbitrary order).

由于重复条目在算法中并不是真正有用，因此必须对其进行特殊处理。

删除最小组合的adjust 函数会不断调整优先级队列，直到可以确保删除所有重复的最小元素为止:

adjust table
    | n <= x = adjust (PQ.deleteMinAndInsert n_ ns table)
    | otherwise = table
    where ...

如果当前第一个元素 (n) 小到足以被删除，adjust 会再次调用自身以检查剩余队列中的下一个元素。只有当没有剩余的小元素时，它才会停止递归。