Алгоритм Мейселя – Лемера - Meissel–Lehmer algorithm

Алгоритм Meissel-Лехмер (после того, как Эрнст Меиссел и Derrick Генри Лехмер ) является алгоритм , который вычисляет функцию прайм-подсчета .

Описание

Ключевая личность

Учитывая , можно определить следующие функции: Во-первых, ${\ Displaystyle а \ в \ mathbb {N}}$

${\ displaystyle \ varphi (x, a): = \ left | \ left ([1, x] \ cap \ mathbb {N} \ right) \ setminus \ bigcup _ {j = 1} ^ {a} p_ {j } \ mathbb {Z} \ right |;}$

эта функция измеряет набор (закрытый интервал ), когда отсеиваются числа, кратные первым простым числам ( включая сами эти простые числа); то есть последовательность простых чисел в порядке возрастания. ${\ displaystyle [1, x] \ cap \ mathbb {N}}$${\ displaystyle a}$${\ displaystyle p_ {1}, \ ldots, p_ {a}}$${\ Displaystyle p_ {1}, p_ {2}, p_ {3}, \ ldots = 2,3,5, \ ldots}$

Мы можем дополнительно разделить это на функции

${\ displaystyle P_ {k} (x, a): = \ left | \ left [\ left ([1, x] \ cap \ mathbb {N} \ right) \ setminus \ bigcup _ {j = 1} ^ { a} p_ {j} \ mathbb {Z} \ right] \ cap \ {n \ mid n {\ text {имеет ровно}} k {\ text {простые множители}} \} \ right |,}$

${\ Displaystyle к \ в \ mathbb {N} _ {0};}$

они измеряют множество, но учитывают только числа, имеющие в точности простые множители (это хорошо определено основной теоремой арифметики ). С этим у нас есть ${\ displaystyle \ left ([1, x] \ cap \ mathbb {N} \ right) \ setminus \ bigcup _ {j = 1} ^ {a} p_ {j} \ mathbb {Z}}$${\ displaystyle k}$

${\ displaystyle \ varphi (x, a) = \ sum _ {k = 0} ^ {\ infty} P_ {k} (x, a);}$

сумма справа конечна, так как числа имеют, например, простые множители. ${\ displaystyle \ leq x}$${\ Displaystyle \ Leq \ lfloor x \ rfloor}$

Личности

${\ displaystyle \ pi (x) = P_ {1} (x, a) + a = a + \ varphi (x, a) -1- \ sum _ {k = 2} ^ {\ infty} P_ {k} ( x, a) \ qquad {\ text {(note}} P_ {0} (x, a) = 1)}$

доказать , что один может вычислить путем вычисления и , . И это то, что делает алгоритм Мейселя – Лемера. ${\ Displaystyle \ пи (х)}$${\ Displaystyle \ varphi (х, а)}$${\ Displaystyle P_ {k} (х, а)}$${\ Displaystyle к \ geq 2}$

Формулы для P _k ( x , a )

Для , мы получаем следующую формулу для : ${\ displaystyle k = 2}$${\ Displaystyle P_ {k} (х, а)}$

${\ displaystyle {\ begin {align} P_ {2} (x, a) & = \ left | \ left \ {n \ mid n \ leq x, n = p_ {b} p_ {c}, a <b \ leq c \ right \} \ right | \\ & = \ sum _ {b = a + 1} ^ {\ pi (x ^ {1/2})} \ left | \ left \ {n ~ {\ big | } ~ n = p_ {b} p_ {c}, b \ leq c \ leq \ pi \ left ({\ frac {x} {p_ {b}}} \ right) \ right \} \ right | \\ & = \ sum _ {b = a + 1} ^ {\ pi (x ^ {1/2})} \ left (\ pi \ left ({\ frac {x} {p_ {b}}} \ right) - (b-1) \ right) \\ & = \ sum _ {b = a + 1} ^ {\ pi (x ^ {1/2})} \ pi \ left ({\ frac {x} {p_ { b}}} \ right) + {\ binom {a} {2}} - {\ binom {\ pi (x ^ {1/2})} {2}}. \ end {align}}}$

Для есть аналогичное расширение. ${\ displaystyle k = 3}$

Раскладывая 𝜑 ( x , a )

Используя формулу

${\ displaystyle \ varphi (x, a) = \ varphi (x, a-1) - \ varphi \ left ({\ frac {x} {p_ {a}}}, a-1 \ right),}$

${\ Displaystyle \ varphi (х, а)}$ может быть расширен. Каждое слагаемое, в свою очередь, может быть разложено таким же образом, так что возникает очень большая переменная сумма.

Комбинируя термины

Единственное, что остается сделать, это оценить и для определенных значений и . Это можно сделать прямым просеиванием и использованием вышеуказанных формул. ${\ Displaystyle \ varphi (х, а)}$${\ Displaystyle P_ {к} (х, а), к = 1,2, \ ldots}$${\ displaystyle x}$${\ displaystyle a}$

Современный вариант

Джеффри Лагариас , Виктор Миллер и Эндрю Одлыжко опубликовали реализацию этого алгоритма, который вычисляет во времени и пространстве для любого . После настройки дерево имеет листовые узлы. ${\ Displaystyle \ пи (х)}$${\ Displaystyle О (х ^ {2/3 + \ varepsilon})}$${\ Displaystyle О (х ^ {1/3 + \ varepsilon})}$${\ displaystyle \ varepsilon> 0}$${\ Displaystyle а = \ пи (х ^ {1/3})}$${\ Displaystyle \ varphi (х, а)}$${\ Displaystyle О (х ^ {2/3})}$

Рекомендации