Подлинное сито Эратосфена - алгоритм, используемый для генерации простых чисел

Сегодня я прочитал статью:

O'Neill, Melissa E., Подлинная Сито Эратосфена ", Журнал Функциональное программирование, опубликованное онлайн от Cambridge University Press 09 Окт 2008 DOI:. 10,1017/S0956796808007004

Он описал алгоритм генерации простого числа с помощью 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 .. ]

Алгоритм кажется правильным на первый взгляд, но я ничего не понимаю:

Как PQ использует дескриптор минимального приоритета?

Я провел некоторое симуляцию вручную, и я обнаружил, что это может вызвать ошибку.

Если кто-то сможет это объяснить, я буду благодарен за вашу помощь!

Ответы

Ответ 1

В документе говорится об использовании очереди приоритетов:

Учитывая эти потребности, приоритетная очередь является привлекательным выбором, тем более, что эта структура данных поддерживает множество элементы с одинаковым приоритетом (удаление в них произвольного порядка).

Так как дублирующие записи не очень полезны в алгоритме, они должны быть обработаны специально.

Функция adjust, которая удаляет минимальный составной, продолжает корректировать очередь приоритетов, пока не будет уверен, что все дубликаты минимального элемента будут удалены:

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

Если текущий первый элемент (n) был достаточно мал, чтобы его можно было удалить, снова настройте вызовы, чтобы также проверить следующий элемент в оставшейся очереди. Только когда нет маленьких элементов, они перестают рекурсировать.