la criba de Eratóstenes genuino - algoritmo utilizado para generar números primos

Question

Hoy leí un artículo:

O'Neill, Melissa E., "Diario de The Genuine Sieve of Eratosthenes", programación funcional, Publicado en línea por la Universidad de Cambridge prensa 09 Oct 2008 doi: 10.1017./S0956796808007004

Se describe un algoritmo de generación de números primos utilizando cola de prioridad:

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

El algoritmo parece ser correcta, a primera vista, pero no entiendo una cosa:

¿Cómo funciona el PQ se utiliza manejar duplica mínima prioridad?

Hice algunas simulaciones a mano y encontré que podría causar un error.

¡Si alguien pudiera explicarlo, agradeceré su ayuda!

Answer 1

En el documento se dice esto acerca de la cola de prioridad que se utiliza:

Teniendo en cuenta estas necesidades, una cola de prioridad es una opción atractiva, especialmente porque esta estructura de datos soporta de forma nativa múltiples elementos con la misma prioridad (Dequeuing en ellos orden arbitrario).

Dado que las entradas duplicadas no son realmente útiles en el algoritmo, deben tratarse especialmente.

La función adjust, que elimina el material compuesto mínimo, mantiene el ajuste de la cola de prioridad hasta que se pueda estar seguro de que todos los duplicados del elemento mínimo se eliminan:

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

Si el actualmente primer elemento (n) era lo suficientemente pequeño como para eliminarlo, ajuste las llamadas de nuevo también para verificar el siguiente elemento en la cola restante. Solo cuando no quedan elementos pequeños, deja de recurrir.