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.

The trial division test, abstractly formulated, is this: for each number $i$ in some suitable set, check whether $i$ divides $n$. If one such number is found, output "$n$ is composite", else output "$n$ is prime". (Perhaps you need to special-case $n=1$; I'll leave that to the reader).

Clearly no suitable set can contain $1$ or $n$, or we would report all numbers to be composite. No number is divisible by zero, and a number is divisible by $-x$ iff it is divisible by $x$, so we don't need to check numbers less than $1$. Also, if $m > n$ then $m$ does not divide $n$, so the set $\{2..n-1\}$ is definitely good enough: if we check all those numbers (and only those), then we are guaranteed to output the correct answer. It can be large, though, so we would like to thin it out if we can.

How do we guarantee that by using that condition we are actually checking all possible divisors and the rest that we omitted are never going to be divisors?

If $n / i$ is an integer, let's call it $k$, then definitely $n / k = n / (n/i) = i$ is also an integer. In other words, if $n = ik$ with $i < k$, then when you check for $i$ you indirectly also check for $k$: if $n$ can be factored into two non-trivial factors, finding the smaller of the two is finding at least one such factor (from which you can conclude that it's composite), and if $n$ can't be factored so, no such smaller-of-the-two factor will exist.

So, if instead of $\{2..n-1\}$ you only look at from 2 up to the largest of any possible smallest-factor-in-a-pair, you have still looked at enough possible candidates to be certain in your conclusion. Other people have already explained why $\sqrt{n}$ is the limit.

There is some subtlety in why $\lfloor\sqrt{n}\rfloor$, which is really what is being checked, is also good enough: either $\lfloor\sqrt{n}\rfloor = \lceil(\sqrt{n})\rceil = \sqrt{n}$ or $\lceil(\sqrt{n})\rceil^2 > n$, so either you have checked $\lceil(\sqrt{n})\rceil$ also, or you don't need to.