The Genuine Sieve of Eratosthenes -- algorithm used to generate prime numbers.

Question

Today I read a paper:

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.

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!

Answer 1

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

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

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.