El test de primalidad más viejo --e ineficiente

Por hipótesis, $n$ tiene un divisor $a$ con $2\leq a \leq {n-1}$. Es decir, $n=ab$. Y es claro que alguno de los dos factores es $\leq{n}$ --de otra manera se tendría $ab<\sqrt{n}\sqrt{n}=n$ lo cual es imposible.

Ahora bien, a,b pueden a su vez ser primos o compuestos...

Nota sobre el modo de uso: si se tuviera duda sobre si 91 es primo o es compuesto, se obtiene la raíz aproximada que es menor que 10; entonces el test consiste en probar para cada uno de los primos menores que 10 (obviamente no es divisible entre 2,3,5, pero al llegar al 7 se logra $91=7\cdot 13$. ) Si ninguno de esos primos lo dividiera entonces 91 sería primo (por la contrapositiva del lema).