Sieve of Eratosthenes : why can we stop at the $\sqrt n$?

You can argue by contradiction. To make things clear, when I talk about a number's 'prime factors' I'm going to count multiple instances of the same prime distinctly; for instance, $36=2^2\cdot3^2$ has four prime factors: $\{2, 2, 3, 3\}$. (This is sometimes referred to as a multiset of prime factors, but that's an aside...)

Suppose there were a non-prime left after you've sieved up to $\sqrt{n}$. Then it must have at least two prime factors (by definition), and each of those factors must be larger than $\sqrt{n}$ (because that's the guarantee from the sieving you've done). This means that the number itself must be larger than $\sqrt{n}\cdot\sqrt{n}=n$ — but we were only looking at numbers up to $n$.