埃拉托斯特尼筛法的正确性

（$\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]$ 中仍未被标记的每个数都满足右边条件，因而都是质数。