Correctness of the Sieve of Eratosthenes

($\Leftarrow$) Suppose $n$ has no prime factor $\le\sqrt n$. If $n$ were composite, write $n=ab$ with $1<a\le b<n$. Then $a\le\sqrt n$ (otherwise $a>\sqrt n$ and $b\ge a>\sqrt n$ would force $ab>n$, a contradiction), and $a$'s smallest prime factor $p$ satisfies $p\le a\le\sqrt n$, so $p$ is a prime factor of $n$ that is $\le\sqrt n$ — contradicting the hypothesis. So $n$ has no such factorization, hence $n$ is prime.

($\Rightarrow$) If $n$ is prime, its only positive divisors are $1$ and $n$; no prime $p<n$ divides it at all, so in particular none with $p\le\sqrt n$ does either.

Together these show the two conditions are equivalent, which is exactly the termination criterion used in the sieve: after processing every prime up to $\sqrt N$, everything still unmarked in $[2,N]$ satisfies the right-hand side, hence is prime.