A composite number has a prime factor at most its square root

Statement

Let $n$ be a composite number. Then $n$ has a prime factor $p$ with $p^2 \le n$, that is, $p \le \sqrt{n}$.

Remarks

The smallest prime factor $p$ of $n$ has this property. Write $n = p m$. Then $m > 1$, and each prime factor of $m$ is at least $p$, so $m \ge p$ and $n \ge p^2$. This result justifies trial division: to test whether $n > 1$ is prime, it is enough to test the primes $p \le \sqrt{n}$. For example, $\sqrt{97} < 10$ and none of $2, 3, 5, 7$ divides $97$, so $97$ is prime.

Explanations

L1 human

If $n = a b$ with both factors larger than $\sqrt{n}$, then $a b > n$, which is impossible. So one of the two factors is at most $\sqrt{n}$, and a prime factor of that factor is also at most $\sqrt{n}$.