Tính đúng đắn của sàng Eratosthenes

($\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ố.