筛法

这个等价关系正是使筛法能够提前停止的原因：一旦直到 $\sqrt N$ 的所有质数都划去了它们的倍数，就再没有任何证据能证明剩下的数是合数，因此再检验（或划去）更大质数的倍数被证明是白费功夫。

（$\Leftarrow$）设 $n$ 没有 $\le\sqrt n$ 的质因数。若 $n$ 是合数，记 $n=ab$，$1<a\le b<n$。则 $a\le\sqrt n$（否则 $a>\sqrt n$ 且 $b\ge a>\sqrt n$ 将迫使 $ab>n$，矛盾），而 $a$ 的最小质因数 $p$ 满足 $p\le a\le\sqrt n$，故 $p$ 是 $n$ 的一个 $\le\sqrt n$ 的质因数——与假设矛盾。因此 $n$ 不存在这样的分解，故 $n$ 是质数。

（$\Rightarrow$）若 $n$ 是质数，其正因数只有 $1$ 和 $n$；没有任何质数 $p<n$ 整除它，特别地满足 $p\le\sqrt n$ 的质数也不整除。

两者合起来说明这两个条件等价，这正是筛法中使用的终止判据：处理完直到 $\sqrt N$ 的所有质数后，$[2,N]$ 中仍未被标记的每个数都满足右边条件，因而都是质数。

这是"划去倍数"这一操作精确的定量版本：它不再在网格上物理标记，而是直接用容斥原理，根据哪些小质数整除它们来计数幸存者。它是所有用于攻克孪生质数与有界间隔的现代筛法（布伦筛、塞尔伯格筛、大筛法、GPY筛法）的鼻祖——归根结底，它们都是更巧妙地控制这个精确公式所产生的误差项的方法。

任意整数 $a\in A$ 与 $P(z)$ 互素当且仅当它不被任何满足 $p<z$ 的质数整除。对每个因子 $d\mid P(z)$（这些质数某子集的无平方乘积），$A=\{1,\ldots,x\}$ 中 $d$ 的倍数个数恰为 $\lfloor x/d\rfloor$。

对事件"$p\mid a$"（$p<z$）用容斥原理：被 $\mathcal P$ 中至少一个质数整除的 $a\in A$ 个数为 $\sum_{p<z}\lfloor x/p\rfloor - \sum_{p<q}\lfloor x/(pq)\rfloor + \sum_{p<q<r}\lfloor x/(pqr)\rfloor - \cdots$，符号随相乘的质数个数交替。每个这样的交替符号恰好就是对应无平方 $d\mid P(z)$ 的莫比乌斯函数 $\mu(d)$：$\mu(1)=1$，$d$ 为 $k$ 个不同质数之积时 $\mu(d)=(-1)^k$。

因此被 $\mathcal P$ 中至少一个质数整除的个数为 $-\sum_{d\mid P(z),\,d>1}\mu(d)\lfloor x/d\rfloor$。用 $|A|=\lfloor x\rfloor=x$（$d=1$ 项，$\mu(1)\lfloor x/1\rfloor=x$）减去它，即得与 $P(z)$ 互素的个数：$S(A,\mathcal P,z)=x-\sum_{d\mid P(z),d>1}\mu(d)\lfloor x/d\rfloor=\sum_{d\mid P(z)}\mu(d)\lfloor x/d\rfloor$。

最后，取 $z=\sqrt x+1$，使 $\mathcal P$ 恰为 $\le\sqrt x$ 的质数：任何与它们全部互素的 $a\in[2,x]$ 要么是 $1$，要么是 $>\sqrt x$ 的质数（由上面的定理，因为它没有 $\le\sqrt x$ 的质因数），故 $S(A,\mathcal P,\sqrt x+1)=1+\big(\pi(x)-\pi(\sqrt x)\big)$，即得所述恒等式。