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

问题描述

今天我读了一篇论文：

由于重复的条目在他们拥有的算法中并不真正有用e将被特别处理。

调整函数删除最小合成，不断调整优先级队列直到可以肯定的是，最小元素的所有重复项都被删除：

 调整表
 | n< = x = adjust（PQ.deleteMinAndInsert n_ns表）
 |否则=表
其中... 
  

如果当前第一个元素（ n ）足够小，可以被移除，再次调整自身以检查剩余队列中的下一个元素。只有当没有小元素时，它才会停止递归。

Today I read a paper:

It described an algorithm of generating prime number by using Priority Queue :

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 .. ]

The algorithm seems to be correct at first glance, but I don't understand one thing:

How does the PQ it uses handle duplicated minimal priority?

I made some simulation by hand and I found that might cause an error.

If some one could explain it, I will appreciate your help!

解决方案

The paper says this about the priority queue that is being used:

Since duplicate entries are not really useful in the algorithm they have to be treated specially.

The adjust function, which removes the minimal composite, keeps adjusting the priority queue until it can be sure that all duplicates of the minimal element are removed:

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

If the currently first element (n) was small enough to be removed, adjust calls itself again to also check the next element in the remaining queue. Only when there are no small elements left it stops recursing.

这篇关于Eratosthenes真正的筛 - 用于生成素数的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！