Sàng Legendre (đếm bằng bù trừ)

Mọi số nguyên $a\in A$ nguyên tố cùng $P(z)$ khi và chỉ khi không chia hết cho bất kỳ số nguyên tố $p<z$ nào. Với mỗi ước $d\mid P(z)$ (tích không chính phương của một tập con các số nguyên tố này), số bội của $d$ trong $A=\{1,\ldots,x\}$ chính xác là $\lfloor x/d\rfloor$.

Theo bù trừ trên các biến cố "$p\mid a$" với $p<z$: số $a\in A$ chia hết bởi ít nhất một số nguyên tố trong $\mathcal P$ là $\sum_{p<z}\lfloor x/p\rfloor - \sum_{p<q}\lfloor x/(pq)\rfloor + \sum_{p<q<r}\lfloor x/(pqr)\rfloor - \cdots$, đổi dấu theo số lượng số nguyên tố nhân lại. Mỗi dấu đổi như vậy chính xác là hàm Möbius $\mu(d)$ của $d\mid P(z)$ không chính phương tương ứng: $\mu(1)=1$, $\mu(d)=(-1)^k$ với $d$ là tích $k$ số nguyên tố khác nhau.

Vậy số chia hết bởi ít nhất một số nguyên tố trong $\mathcal P$ là $-\sum_{d\mid P(z),\,d>1}\mu(d)\lfloor x/d\rfloor$. Trừ điều này khỏi $|A|=\lfloor x\rfloor=x$ (số hạng $d=1$, $\mu(1)\lfloor x/1\rfloor=x$) cho số nguyên tố cùng $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$.

Cuối cùng, lấy $z=\sqrt x+1$ để $\mathcal P$ chính xác là các số nguyên tố $\le\sqrt x$: bất kỳ $a\in[2,x]$ nguyên tố cùng mọi số này hoặc là $1$ hoặc là số nguyên tố $>\sqrt x$ (theo định lý ở trên, vì nó không có thừa số nguyên tố $\le\sqrt x$), nên $S(A,\mathcal P,\sqrt x+1)=1+\big(\pi(x)-\pi(\sqrt x)\big)$, cho đẳng thức đã nêu.