勒让德筛法

在数学上，勒让德筛法（Legendre sieve）是现代筛法中最简单的，其以阿德里安-马里·勒让德为名。这筛法是埃拉托斯特尼筛法的概念的推广，用以找出一个给定的集合中质数数量的上下界。由于这筛法是埃拉托斯特尼概念的简单推广之故，因此有时又称作勒让德—埃拉托斯特尼筛法（Legendre–Eratosthenes sieve）。^[1]

勒让德等式

勒让德筛法的中心概念可以下列等式表示，有时这等式又称作勒让德等式（Legendre identity）：

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

在其中，${\displaystyle A}$是一个整数集、${\displaystyle P}$是不同质数的乘积，${\displaystyle \mu }$是默比乌斯函数；而${\displaystyle A_{d}}$是${\displaystyle A}$中可被${\displaystyle d}$除尽的元素的集合，是${\displaystyle A}$的子集；而${\displaystyle S(A,P)}$的定义如次：

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

换句话说，${\displaystyle S(A,P)}$指的是${\displaystyle A}$中与${\displaystyle P}$互质的元素的个数。

当注意的是，在多数情况中，${\displaystyle A}$是所有小于特定实数${\displaystyle X}$的整数的集合，${\displaystyle P}$是所有小于等于特定整数${\displaystyle z}$的质数的乘积，且${\displaystyle z<X}$，因此勒让德等式可以下式表示（其中${\displaystyle \lfloor X\rfloor }$是下取整函数）：

${\displaystyle {\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}}}$

至此勒让德等式衍生自埃拉托斯特尼筛法变得明朗：上式中的第一项表示所有小于${\displaystyle X}$的整数，第二项则去掉其中至少是一个质数倍数的数，第三项则将其中至少是两个质数倍数的数给补回（会有第三项是因为第二项会把两个质数倍数的数给错误地删去两次之故），但因为这样又多补回一次至少是三个质数倍数的数，因此第三项中又要将之删去，其余以此类退，直到所有质数的${\displaystyle 2^{\pi (z)}}$个组合全部都考虑过为止。（${\displaystyle \pi (z)}$指的是小于${\displaystyle z}$的质数的数量）。

在完成对${\displaystyle S(A,P)}$的计算后，就可以下式求出${\displaystyle \pi (X)}$的上界：

${\displaystyle S(A,P)\geq \pi (X)-\pi (z)+1,\,}$

而这上界可由${\displaystyle S(A,P)}$的定义立即得出。

限制

勒让德筛法的一个问题是余项部分会逐渐累积出一个巨大的误差，而这表示说这筛法在多数状况下，只能给出一个非常弱的上下界。因此这筛法在实务中几乎不使用，而学者一般都使用布朗筛法或塞尔伯格筛法等其他技巧；然而，由于更加强力的筛法皆衍生自勒让德筛法的基本概念之故，因此了解勒让德筛法的原理，依旧是有用的。

参考资料

1. Iwaniec, Henryk. The sieve of Eratosthenes–Legendre （页面存档备份，存于互联网档案馆）. Annali della Scuola Normale Superiore di Pisa – Classe di Scienze, Sér. 4, 4 no. 2 (1977), pp. 257–268 MR 453676 （页面存档备份，存于互联网档案馆） （页面存档备份，存于互联网档案馆）