§ Why searching for divisors upto sqrt(n) works

• It's not that all divisors are smaller than $\sqrt n$. For example, consider $14 = 7 \times 2$. $\sqrt{14} \sim 4$, but one of its diviors ( $7$) is greater than 4.
• Rather, it is that if there is a divisor $l$ (for large) which is larger than $\sqrt n$, there will be another divisor $s$ which is smaller than $\sqrt n$.
• Proof: Suppose $l \div n$, $l \geq \sqrt n$. So there exists an $s$ such that $ls = n$, or $s = n / l$.
• Since $l \geq \sqrt n$, $n / l \leq n / \sqrt n = \sqrt n$. Thus $s \leq \sqrt n$.
• So if we wish to find some factor of $n$, we can simply search within the range $\sqrt n$.
• If $n$ has no factors in the range $\sqrt n$, then $n$ must be prime, for if $n$ did have a larger factor, $n$ would also have a smaller factor we would have found.