Il vero Crivello di Eratostene - algoritmo utilizzato per generare numeri primi

Question

Oggi ho letto un articolo:

O'Neill, Melissa E., "The Genuine Sieve of Eratosthenes", ufficiale programmazione funzionale, pubblicato on-line dalla Cambridge University Press 9 ottobre 2008 doi:. 10,1017/S0956796808007004

E 'descritto un algoritmo di generazione di numeri primi utilizzando coda Priorità:

0.123.516,41 mila

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

L'algoritmo sembra essere corretta a prima vista, ma non capisco una cosa:

Come funziona il PQ usa gestire duplicato priorità minima?

Ho eseguito alcune simulazioni a mano e ho scoperto che potrebbe causare un errore.

Se qualcuno potrebbe spiegarlo, apprezzerò il vostro aiuto!

Answer 1

Il giornale dice questo circa la coda di priorità che viene utilizzato:

Date queste esigenze, una coda di priorità è una soluzione accattivante, soprattutto perché questa struttura dati supporta in modo nativo multipla oggetti con la stessa priorità (dequeuing in loro ordine arbitrario).

Poiché le voci duplicate non sono realmente utili nell'algoritmo devono essere trattate in modo speciale.

La funzione adjust, che rimuove il composito minimo, mantiene regolando la coda di priorità finché non può essere sicuro che tutti i duplicati dell'elemento minimo vengono rimossi:

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

Se attualmente primo elemento (n) era abbastanza piccolo da essere rimosso, regolare di nuovo le chiamate per controllare anche l'elemento successivo nella coda rimanente. Solo quando non ci sono piccoli elementi rimasti, si arresta.