Why it is enough to stop at the square root of N

Why can one stop in the sieve when $p^2>N$? The reason is simple and concerns every composite number.

Remark — Why it is enough to stop at $\sqrt{N}$

If $n\le N$ were composite, then $n=a\cdot b$ with $1<a\le b$. It follows that $a\le\sqrt{n}\le\sqrt{N}$: the smaller factor is $\le\sqrt{N}$. So every composite number $\le N$ has a prime factor $\le\sqrt{N}$ and has already been crossed out when the multiples of the primes up to $\sqrt{N}$ were eliminated. The cost of the sieve is $O(N\log\log N)$: for $N=10^6$ a few milliseconds are enough.

Links

Topics: Numbers and operations
Concepts: Sieve of Eratosthenes · Prime number
Skills: Prove