Contenido principal
Curso: Ciencias de la computación > Unidad 2
Lección 6: Prueba de primalidadDivisión por tentativa
Google ClassroomDefinir el problema
Necesitamos construir una máquina que pueda responder preguntas sencillas de tipo sí/no. Dado un número entero n como entrada, ¿n es 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 buscaste 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? SÍ
Encontramos un divisor de 49 (7), lo que prueba que 49 es un número compuesto.
Construir una pared
Sin embargo, ¿qué pasaría si te pregunto si 2971215073 es primo?
¿Todavía lo estás revisando? Después de las primeras mil revisiones, yo sigo sin encontrar un divisor. La pregunta clave es: ¿cuándo podemos dejar de revisar y probar que n es primo? (llamémosle a esto nuestra pared). Como punto de partida, sabemos que nuestra pared debe ser n-1 (ya que n divide a n). Si revisamos hasta 2971215072 encontramos un divisor (lo cual prueba que n es compuesto) O no lo encontramos (lo cual que prueba que n es primo).
Construir 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 = 33) o 49 (49 = 77). 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 en {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 tu información, es posible realizar esta lección sin hacer nada de programación).
¿Quieres unirte a la conversación?
Sin publicaciones aún.