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

Question

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

О'Нил, Мелисса Э., " Подлинная Сито Эратосфена ", Журнал Функциональное программирование, опубликовано онлайн издательством Кембриджского университета 09 октября 2008 DOI: 10,1017 / S0956796808007004

.

В нем описан алгоритм генерации простого числа с использованием очереди приоритетов:

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 использует дублирующий минимальный приоритет?

Я провел некоторое моделирование вручную и обнаружил, что это может привести к ошибке.

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

Answer 1

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

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

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

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

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

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