Comprobar si un número es primo en Python
En esta lección vas a comprobar si un número es primo probando los divisores solo hasta su raíz cuadrada.
Introducción
El problema
Los números primos están detrás del cifrado en internet, de las tablas hash y de muchos acertijos. Comprobar si un número es primo probando todos los divisores hasta el propio número funciona con 29, pero se vuelve muy lento con números grandes. Una pequeña idea hace la comprobación mucho más rápida.
Imagínalo así
Buscar divisores es como intentar colocar baldosas formando un rectángulo completo. 36 baldosas caben como 1×36, 2×18, 3×12, 4×9 y 6×6. Después del cuadrado (6×6) vuelven a salir los mismos rectángulos, solo que girados, así que más allá de la raíz cuadrada no hay nada nuevo que encontrar. 29 baldosas solo caben como 1×29, por eso 29 es primo.
number > 1🚪 Solo los números mayores que 1 pueden ser primosdivisor * divisor <= number🪞 Para en el cuadrado: los rectángulos que siguen son repetidosnumber % divisor == 0🔍 Sale un rectángulo completo: no es primodivisor += 1➡️ Prueba el siguiente anchoUn número primo es un número entero mayor que 1 cuyos únicos divisores positivos son 1 y él mismo.
Puntos clave
is_prime = number > 1empieza siendo False para 0, 1 y los negativos, que nunca son primos.while divisor * divisor <= number and is_prime:se detiene en la raíz cuadrada o en cuanto encuentra un divisor.number % divisor == 0significa quedivisordivide exactamente al número.- Para 29, el bucle solo prueba 2, 3, 4 y 5 antes de poder decir que es primo.
¿Cuándo se usa?
- Acertijos y ejercicios con números, como listar primos o encontrar factores primos.
- Aprender por qué parar antes y comprobar solo hasta un límite hacen más rápidos los bucles.
- Validar entradas en herramientas de matemáticas.
Cuándo no hace falta
- Listar todos los primos hasta un límite grande: la criba de Eratóstenes es mucho más rápida que comprobar cada número.
- Criptografía con números de cientos de dígitos: los sistemas reales usan pruebas probabilísticas.
Código de ejemplo
number = 29
is_prime = number > 1
divisor = 2
while divisor * divisor <= number and is_prime:
if number % divisor == 0:
is_prime = False
divisor += 1
print(f"{number} is prime: {is_prime}")
Resultado de la ejecución
29 is prime: True
Explicación del código
El bucle solo necesita probar divisores mientras divisor * divisor <= number. Si n tiene un divisor mayor que su raíz cuadrada, ese divisor va emparejado con otro más pequeño que el bucle ya ha probado. Así la complejidad baja a O(√n), y el resultado muestra que 29 es primo.
Cambia los valores y ejecuta el programa en el compilador Python online de CodeUtility sin instalar Python.
Ejercicios de práctica
Prueba a modificar el código siguiendo las ideas de abajo. Cambiar el código y ver el resultado te ayudará a entender la lección mucho mejor que solo leerla.
- Cambia los datos de entrada y predice el resultado antes de ejecutar.
- Añade una comprobación para datos vacíos o no válidos.
- Pasa el proceso a una función aparte y pruébala con varios conjuntos de datos.
Errores comunes
Tratar el 1 como primo
El 1 solo tiene un divisor, así que no es primo. Comprueba primero number > 1.
is_prime = True # 1 would be reported as prime
is_prime = number > 1
Recorrer hasta el propio número
Da la respuesta correcta, pero prueba muchos más divisores de los necesarios.
for divisor in range(2, number):
while divisor * divisor <= number:
¿Terminaste esta lección?
Márcala como aprendida para seguir tu progreso.
Practica con un reto
Usa lo que cubre esta lección para resolver un problema real. Cada reto se ejecuta en el navegador, con pruebas al instante y una revisión de IA.
- Verificación de número primo Determina si un número es primo. Fácil
- Mayor Factor Primo Encuentra el mayor número primo que divide a un entero positivo. Intermedio
- Listar Primos con un Criba Encuentra números primos hasta un límite marcando los múltiplos compuestos. Intermedio