Алгоритм Meissel-Лехмер (после того, как Эрнст Меиссел и Derrick Генри Лехмер ) является алгоритм , который вычисляет функцию прайм-подсчета .
Описание
Ключевая личность
Учитывая , можно определить следующие функции: Во-первых,
эта функция измеряет набор (закрытый интервал ), когда отсеиваются числа, кратные первым простым числам ( включая сами эти простые числа); то есть последовательность простых чисел в порядке возрастания.
Мы можем дополнительно разделить это на функции
они измеряют множество, но учитывают только числа, имеющие в точности простые множители (это хорошо определено основной теоремой арифметики ). С этим у нас есть
сумма справа конечна, так как числа имеют, например, простые множители.
Личности
доказать , что один может вычислить путем вычисления и , . И это то, что делает алгоритм Мейселя – Лемера.
Формулы для P k ( x , a )
Для , мы получаем следующую формулу для :
Для есть аналогичное расширение.
Раскладывая 𝜑 ( x , a )
Используя формулу
может быть расширен. Каждое слагаемое, в свою очередь, может быть разложено таким же образом, так что возникает очень большая переменная сумма.
Комбинируя термины
Единственное, что остается сделать, это оценить и для определенных значений и . Это можно сделать прямым просеиванием и использованием вышеуказанных формул.
Современный вариант
Джеффри Лагариас , Виктор Миллер и Эндрю Одлыжко опубликовали реализацию этого алгоритма, который вычисляет во времени и пространстве для любого . После настройки дерево имеет листовые узлы.
Рекомендации