Phương pháp sàng

Sự tương đương này chính xác là điều cho phép sàng dừng sớm: khi mọi số nguyên tố tới $\sqrt N$ đã đánh dấu bội của nó xong, không còn nhân chứng nào có thể kết tội bất kỳ số còn lại là hợp số, nên kiểm tra (hay đánh dấu) các số nguyên tố lớn hơn được chứng minh là công việc lãng phí.

($\Leftarrow$) Giả sử $n$ không có thừa số nguyên tố $\le\sqrt n$. Nếu $n$ là hợp số, viết $n=ab$ với $1<a\le b<n$. Khi đó $a\le\sqrt n$ (nếu không $a>\sqrt n$ và $b\ge a>\sqrt n$ sẽ buộc $ab>n$, mâu thuẫn), và thừa số nguyên tố nhỏ nhất $p$ của $a$ thỏa $p\le a\le\sqrt n$, nên $p$ là thừa số nguyên tố của $n$ với $\le\sqrt n$ — mâu thuẫn giả thiết. Vậy $n$ không có phân tích như vậy, nên $n$ là nguyên tố.

($\Rightarrow$) Nếu $n$ là nguyên tố, ước dương duy nhất của nó là $1$ và $n$; không số nguyên tố $p<n$ nào chia hết nó cả, nên đặc biệt không số nào với $p\le\sqrt n$ chia hết.

Cùng nhau, hai điều này cho thấy hai điều kiện tương đương, chính xác là tiêu chí dừng dùng trong sàng: sau khi xử lý mọi số nguyên tố tới $\sqrt N$, mọi thứ còn chưa đánh dấu trong $[2,N]$ thỏa vế phải, do đó là nguyên tố.

Đây là phiên bản chính xác, định lượng của "gạch bỏ bội số": thay vì đánh dấu vật lý trên lưới, nó đếm trực tiếp số sống sót bằng bù trừ trên các số nguyên tố nhỏ chia hết chúng. Đây là tổ tiên của mọi sàng hiện đại (Brun, Selberg, sàng lớn, GPY) dùng để tấn công số nguyên tố sinh đôi và khoảng cách bị chặn — tất cả về cơ bản đều là những cách thông minh hơn để kiểm soát các số hạng sai số mà chính công thức này sinh ra.

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.