خوارزمية مايسل-ليمر

ليكن p₁ _, p₂ _, … , pₙ الأعداد الأولية n الأولى . بالنسبة لعدد طبيعي a ≥ 1 ، _عرّف

${\displaystyle \varphi (x,a):=\left|\left\{n\leq x:p|n\implies p>p_{a}\right\}\right|,}$

والذي يحسب الأعداد الطبيعية التي لا تزيد عن x والتي جميع عواملها الأولية أكبر من p _. عرّف أيضًا للعدد الطبيعي k ،

${\displaystyle P_{k}(x,a):=\left|\left\{n\leq x:n=q_{1}q_{2}\cdots q_{k},~{\text{مع}}~q_{1},\ldots ,q_{k}>p_{a}\right\}\right|,}$

والتي تحسب الأعداد الطبيعية التي لا تزيد عن x والتي لها k عوامل أولية بالضبط ، وكلها أكبر من p _. باستخدام هذه الأعداد، لدينا

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

حيث أن المجموع يحتوي فقط على عدد محدود من الحدود غير الصفرية لأن P k ( x , a ) = 0 عندما p ka  > x . باستخدام حقيقة أن P 0 ( x , a ) = 1 و P 1 ( x , a ) = π ( x ) - a ، نحصل على

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

وهذا يثبت أنه يمكن حساب π ( x ) _عن طريق حساب φ ( x , a ) و Pk ( x , a ) لـ k ≥ 2. وهذا ما تفعله خوارزمية مايسل-ليمر.

بالنسبة لـ k = 2 ، نحصل على الصيغة التالية لـ P _k ( x , a ) :

$\displaystyle \begin{aligned}P_{2}(x,a)&=\left|\left\{n:n\leq x,~n=p_{b}p_{c},~{\text{مع}}~a<b\leq c\right\}\right|\\&=\sum _{b=a+1}^{\pi (x^{1/2})}\left|\left\{n:n\leq x,~n=p_{b}p_{c},~{\text{مع}}~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 \beginom {x}{p_{b}}}\right)-(b-1)\right)\\&={\binom {a}{2}}-{\binom {\pi (x^{1/2})}{2}}+\sum _{b=a+1}^{\pi (x^{1/2})}\pi \left({\frac {x}{p_{b}}}\right).\end{aligned}}}$

بالنسبة لـ k ≥ 3 ، يمكن اشتقاق متطابقات P _k ( x , a ) بشكل مماثل. ^{[ 1 ]}

مع حالة البداية

${\displaystyle \varphi (x,0)=\lfloor x\rfloor ,}$

وتكرارها

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

يمكن حساب كل قيمة لـ φ ( x , a ) بشكل متكرر.

الشيء الوحيد المتبقي هو حساب قيمتي φ(x, a) و Pk( x , a ) لـ k ≥ 2 _، وذلك لقيم معينة من x و a . ويمكن القيام بذلك عن طريق الغربلة المباشرة واستخدام الصيغ المذكورة أعلاه.