Composite Number has Prime Factor not Greater Than its Square Root
Let $n \in \N$ and $n = p_1 \times p_2 \times \cdots \times p_j$, $j \ge 2$, where $p_1, \ldots, p_j \in \Bbb P$ are prime factors of $n$.
Then $\exists p_i \in \Bbb P$ such that $p_i \le \sqrt n$.
Let $n$ be composite such that $n \ge 0$.
From Composite Number has Two Divisors Less Than It, we can write $n = a b$ where $a, b \in \Z$ and $1 < a, b < n$.
Without loss of generality, suppose that $a \le b$.
Let $a > \sqrt n$.
Then $b \ge a > \sqrt n$.
However, if $b \ge a > \sqrt n$ is true, then:
- $n = a b > \sqrt n \sqrt n > n$
This is clearly a contradiction.
- $a \le \sqrt n$
From Absolute Value of Integer is not less than Divisor, we have that $p \le a$ and so:
- $p \le \sqrt n$
- $p \divides n$
Hence the result.
Suppose we are testing a number to see whether it is prime, or so as to find all its divisors.
One way to do this (which may not be the most efficient in all circumstances, but it gets the job done) is to divide it by successively larger primes until you find one that is a factor of the number.
Eventually you're bound to find a prime that is a factor, by Positive Integer Greater than 1 has Prime Divisor.
However, this result tells us that we don't need to go out that far.
If we've tested all the primes up to the square root of our target number without finding a divisor, we don't need to go any further because we know that our target number is prime after all.