勒讓德篩法

在數學上，勒讓德篩法（Legendre sieve）是現代篩法中最簡單的，其以阿德里安-馬里·勒讓德為名。這篩法是埃拉托斯特尼篩法的概念的推廣，用以找出一個給定的集合中質數數量的上下界。由於這篩法是埃拉托斯特尼概念的簡單推廣之故，因此有時又稱作勒讓德—埃拉托斯特尼篩法（Legendre–Eratosthenes sieve）。^[1]

勒讓德等式

勒讓德篩法的中心概念可以下列等式表示，有時這等式又稱作勒讓德等式（Legendre identity）：

S(A,P)=\sum _{a\in A}\sum _{d\mid a;\,d\mid P}\mu (d)=\sum _{d\mid P}\mu (d)|A_{d}|,

在其中， $A$ 是一個整數集、 $P$ 是不同質數的乘積， $\mu$ 是默比烏斯函數；而 $A_{d}$ 是 $A$ 中可被 $d$ 除盡的元素的集合，是 $A$ 的子集；而 $S(A,P)$ 的定義如次：

S(A,P)=|\{n:n\in A,\gcd(n,P)=1\}|

換句話說， $S(A,P)$ 指的是 $A$ 中與 $P$ 互質的元素的個數。

當注意的是，在多數情況中， $A$ 是所有小於特定實數 $X$ 的整數的集合， $P$ 是所有小於等於特定整數 $z$ 的質數的乘積，且 $z<X$ ，因此勒讓德等式可以下式表示（其中 $\lfloor X\rfloor$ 是下取整函數）：

{\begin{aligned}S(A,P)={}&\sum _{d\mid P}\mu (d)\left\lfloor {\frac {X}{d}}\right\rfloor \\[6pt]={}&\lfloor X\rfloor -\sum _{p_{1}\leq z}\left\lfloor {\frac {X}{p_{1}}}\right\rfloor +\sum _{p_{1}<p_{2}\leq z}\left\lfloor {\frac {X}{p_{1}p_{2}}}\right\rfloor \\[4pt]&{}-\sum _{p_{1}<p_{2}<p_{3}\leq z}\left\lfloor {\frac {X}{p_{1}p_{2}p_{3}}}\right\rfloor +\cdots +\mu (P)\left\lfloor {\frac {X}{P}}\right\rfloor \end{aligned}}

至此勒讓德等式衍生自埃拉托斯特尼篩法變得明朗：上式中的第一項表示所有小於 $X$ 的整數，第二項則去掉其中至少是一個質數倍數的數，第三項則將其中至少是兩個質數倍數的數給補回（會有第三項是因為第二項會把兩個質數倍數的數給錯誤地刪去兩次之故），但因為這樣又多補回一次至少是三個質數倍數的數，因此第三項中又要將之刪去，其餘以此類退，直到所有質數的 $2^{\pi (z)}$ 個組合全部都考慮過為止。（ $\pi (z)$ 指的是小於 $z$ 的質數的數量）。