勒让德筛法（容斥计数）

任意整数 $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)$，即得所述恒等式。