Understanding the trial division primality test

If $n$ is not prime, then at least one of the factors of $n$ is at most as large as $\sqrt n$. To see why, let's suppose not. Since $n$ is not prime, $n = ab$ for some $a,b \neq 1$. If both $a$ and $b$ are larger than $\sqrt n$, then $a\cdot b > \sqrt n \cdot \sqrt n = n$. This clearly cannot be!

So you only need to check for factors up to $\sqrt n$.

Note that if $n$ is composite, then $n$ has a non-trivial factor $i$ such that $i \le \sqrt{n}$. Otherwise, any nontrivial factorization $n = ab$ would force $a, b > \sqrt{n}$, so that $n = ab > \sqrt{n}\times \sqrt{n} = n$, a contradiction.