The Simplest Primality Test

$\sqrt{P}/ 2$ can be disposed of with a counter-example: if $P = 9,$ $\sqrt{9} / 2 = 1.5.$ The only value that will be checked is 2, so the algorithm will claim $P$ is prime, but $9 = 3 \times 3 .$

The next largest value (assuming $P > 4 )$ is $\sqrt{P} .$ A failure would happen if a prime number is declared non-prime. We're going to suppose this happens, and show this leads to a contradiction.

Suppose there is some postive integer $A > \sqrt{P}$ that divides $P$ but is not accounted for by the algorithm (that is, we haven't checked integers large enough yet, and the first failure is at $A ).$ That means there is a postive integer $B$ such that $A \times B = P .$ But note that $\sqrt{P}\sqrt{P} = P$ and $A\sqrt{P} > P$ so that for $A \times B$ to equal $P ,$ $B < \sqrt{P} .$ But that means $B$ would be included by the algorithm and $P$ would be declared not prime. Therefore there is no value larger than $\sqrt{P}$ not accounted for by the algorithm.