真正的Eratosthenes筛子 - 用于生成素数的算法

Question

今天我读了一篇论文:

O'Neill,Melissa E.," Eratosthenes的真正筛选",功能编程期刊,由剑桥大学出版社出版2008年10月9日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

该文件说明了正在使用的优先级队列:

鉴于这些需求,优先级队列是一个有吸引力的选择,特别是因为该数据结构本身支持具有相同优先级的多个项目(以任意顺序出列).

由于重复的条目在算法中并不真正有用,因此必须对它们进行特殊处理.

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

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

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