Proof - Reducing prime checking bounds to $\sqrt{n}$

This is a simple proof accompanying my last post on generating primes.


Let $n$ be a non-prime (i.e. composite), then it must have factors $a$ and $b$ less than $n$.

In other words: $n=ab$, with $n>a>1$ and $n>b>1$.

Suppose $a>\sqrt{n}$ and $b>\sqrt{n}$. This would mean $ab>n$. This cannot be as we just stated that $n=ab$.

Thus, the conclusion we draw is that either $a$ or $b$ is less than or equal to $\sqrt{n}$.

Let us say that  it is $a\leq \sqrt{n}$.

Since $a>1$ , there must exist a prime $p$ that divides $a$. Furthermore, $p\leq a$ since it divides $a$.

We saw earlier that $a$ divides $n$. Since $p$  divides $a$, our prime $p$ must divide $n$. This gives us the result we are trying to prove: $p\leq a$ and $a\leq \sqrt{n}$. Therefore: $p\leq a\leq\sqrt{n}$.

Conclusion: If $n$ is not prime, it must have a prime factor (or regular factor) below $\sqrt{n}$. Otherwise, $n$ must be prime.


$\blacksquare$