Definiendo el problema

Necesitamos construir una máquina que pueda responder preguntas sencillas de tipo sí/no. Dado un número entero n como entrada, ¿es n primo?
Pensemos en qué es lo que debería existir dentro de esta máquina para que funcione. Las máquinas solo pueden seguir una secuencia de pasos con base en algunas instrucciones, conocidas como un algoritmo. Para entrar en calor, vamos a averiguar cuál es el algoritmo que está dentro de tu cerebro. Responde la siguiente pregunta: ¿el 49 es primo?
¿No? ¿Cómo lo hiciste? Probablemente usted buscó un divisor de 49 que fuera mayor que 1 y menor que 49. Si no has memorizado tus tablas de multiplicar, entonces naturalmente seguirías esta secuencia:
  • ¿2 divide a 49?     NO
  • ¿3 divide a 49?     NO
  • ¿4 divide a 49?     NO
  • ¿5 divide a 49?     NO
  • ¿6 divide a 49?     NO
  • ¿7 divide a 49?   
Encontramos un divisor de 49 (7), lo que prueba que 49 es un número compuesto.

Construcción de una pared

Sin embargo, ¿qué pasaría si te pregunto si 2971215073 es primo?
¿Lo sigue revisando? Después de las primeras mil pruebas, yo sigo sin encontrar un divisor. La pregunta clave es: ¿cuándo podemos dejar de probar y probar que n es primo? (llamémosle a esto nuestra pared) Como punto de partida, sabemos que nuestra muralla debe ser n-1 (ya que n divide a n). Si probamos números hasta el 2971215072, o bien encontramos un divisor (lo cual prueba que n es compuesto) O no lo encontramos (lo cual que prueba que n es primo).

Construcción de una mejor pared

Esto funcionaría, pero ¿podemos mover nuestra pared para ahorrar tiempo? Recuerda que en realidad estamos buscando el primer divisor (o el más pequeño). Algunas veces el divisor más pequeño podría ser 2, aunque también podría ser mucho más grande. Lo que nos lleva a la pregunta clave: ¿qué tan grande podría ser el divisor más pequeño?
Recuerda que cualquier entero compuesto n está hecho de dos o más primos n= P * P …
P es el más grande cuando n tiene exactamente dos divisores los cuáles son iguales entre sí. A esto se le conoce como número cuadrado como por ejemplo 9 (9 = 3*3) o 49 (49 = 7*7). Para considerar este peor escenario, ¡simplemente construimos nuestra pared en la raíz cuadrada de n!
Convéncete de esto: si no encontramos un divisor de n después de revisar hasta la raíz cuadrada de n, entonces n debe ser primo. Trata de probarlo por ti mismo (hay una prueba al final de este artículo).

Algoritmo de la división por tentativa

Eso es todo, ahora estamos listos para continuar. Primero, vamos a resumir nuestro algoritmo de la división por tentativa:
  • Acepta un entero n como entrada.
  • Para cada entero x de {2 ... sqrt(n)} revisa si x divide a n.
  • Si encuentras un divisor entonces n es compuesto, DE LO CONTRARIO n es primo.
Si tienes experiencia en programación deberías abrir una libreta de CC e intentar hacer que esta función sirva. Si no, puedes ir al siguiente paso donde te proporciono una versión funcional que puedes usar como punto de partida. (Para su información, es posible realizar esta lección sin hacer nada de programación).