Das Original Sieb des Eratosthenes - Algorithmus zur Erzeugung von Primzahlen

Question

Heute las ich ein Papier verwendet:

O'Neill, Melissa E., "The Genuine Sieve of Eratosthenes", Journal of Functional Programming, veröffentlicht Online von der Cambridge University Presse 9. Oktober 2008 doi:. 10,1017/S0956796808007004

Es einen Algorithmus zur Erzeugung von Primzahl beschrieben von Priority Queue mit:

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

Der Algorithmus scheint auf den ersten Blick korrekt zu sein, aber ich verstehe nicht, eine Sache:

Wie funktioniert die PQ damit umgehen minimale Priorität dupliziert verwendet?

Ich habe einige Simulation von Hand gemacht und ich habe festgestellt, dass dies zu einem Fehler führen könnte.

Wenn jemand es erklären könnte, würde ich Ihre Hilfe zu schätzen wissen!

Answer 1

Das Papier sagt dies über die Prioritätswarteschlange, die verwendet wird:

diese Bedürfnisse gegeben, eine Prioritätswarteschlange ist eine attraktive Wahl, zumal diese Datenstruktur nativ mehr Elemente mit der gleichen Priorität unterstützt (in ihnen willkürliche Reihenfolge austretend).

Da doppelte Einträge im Algorithmus nicht wirklich nützlich sind, müssen sie speziell behandelt werden.

Die adjust Funktion, die den minimalen zusammengesetzten entfernt, hält die Prioritätswarteschlange eingestellt, bis er sicher sein kann, dass alle Duplikate des minimal Element entfernt werden:

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

Wenn der aktuell erste Element (n) wurde klein genug, um entfernt zu werden, passe Anrufe selbst an, um auch das nächste Element in der verbleibenden Warteschlange zu überprüfen. Nur wenn keine kleinen Elemente übrig sind, hört es auf zu rekursiv zu werden.