why check all primes under the root of an interger? I am in high school and I need to factorize numbers. My teacher told me to check all numbers which are smaller than the root of the number I want to factorize. This seems to work just fine, but I do not know why it works and neither does my teacher.
Is there someone here who knows why this trick works?

*

*If there is one factor $a$ that divides $n$, and $a\ge\sqrt n$, then $b=\frac na$ also divides $n$ and $b\le\frac n{\sqrt{n}}=\sqrt{n}$.
In other words, if there is a factor greather than the square root of $n$ there is also a factor lesser that that root.

*If there is a non-prime factor $a$ that divides $n$, then any factor of $a$, including all its prime factors, divide $n$.
So, once you find a prime $p$ between $2$ (included) and $\sqrt n$, you have simplified the problem by having $n/p$ an easier number to check.  If you don't find that $p$ means that $n$ is prime.
