¿Por qué comprobamos hasta la raíz cuadrada de un número para determinar si es primo?
Para comprobar si un número es primo o no, ¿por qué tenemos que comprobar si es divisible sólo hasta la raíz cuadrada de ese número?
Si un número nno es primo, se puede factorizar en dos factores ay b:
n = a * b
Ahora ay bno pueden ser ambos mayores que la raíz cuadrada de n, ya que entonces el producto a * bsería mayor que sqrt(n) * sqrt(n) = n. Entonces, en cualquier factorización de n, al menos uno de los factores debe ser menor o igual que la raíz cuadrada de n, y si no podemos encontrar ningún factor menor o igual a la raíz cuadrada, ndebe ser primo.
Digamos m = sqrt(n)entonces m × m = n. Ahora bien, si nno es primo, entonces nse puede escribir como n = a × b, entonces m × m = a × b. Observe que mes un número real mientras que ny ason bnúmeros naturales.
Ahora pueden darse 3 casos:
- a > m ⇒ b < m
- a = m ⇒ b = m
- a < m ⇒ b > m
En los 3 casos, min(a, b) ≤ m. Por lo tanto, si buscamos hasta m, seguramente encontraremos al menos un factor de n, que es suficiente para demostrar que nno es primo.
Porque si un factor es mayor que la raíz cuadrada de n, el otro factor que se multiplicaría con él para igualar n es necesariamente menor que la raíz cuadrada de n.
Supongamos nque no es un número primo (mayor que 1). Entonces hay números ay btales que
n = ab (1 < a <= b < n)
Multiplicando la relación a<=bpor ay bobtenemos:
a^2 <= ab
ab <= b^2
Por lo tanto: (tenga en cuenta que n=ab)
a^2 <= n <= b^2
Por lo tanto: (Tenga en cuenta que ay bson positivos)
a <= sqrt(n) <= b
Entonces, si un número (mayor que 1) no es primo y probamos la divisibilidad hasta la raíz cuadrada del número, encontraremos uno de los factores.
En realidad, se trata solo de usos básicos de factorización y raíces cuadradas.
Puede parecer abstracto, pero en realidad simplemente radica en el hecho de que el máximo factorial posible de un número no primo tendría que ser su raíz cuadrada porque:
sqrroot(n) * sqrroot(n) = n.
Dado que, si cualquier número entero arriba 1, abajo o hasta se sqrroot(n)divide uniformemente entre n, entonces nno puede ser un número primo.
Ejemplo de pseudocódigo:
i = 2;
is_prime = true;
while loop (i <= sqrroot(n))
{
if (n % i == 0)
{
is_prime = false;
exit while;
}
++i;
}
