Este tutorial le enseñará cómo escribir un programa en Python para comprobar si un número es primo o no.
Si alguna vez ha realizado pruebas de codificación, se habrá encontrado con la pregunta de matemáticas en la prueba de primalidad o para verificar si un número es primo. Y en los próximos minutos, aprenderá a encontrar la solución óptima para esta pregunta.
En este tutorial, usted:
- repasar los conceptos básicos de los números primos,
- escribir código Python para verificar si un número es primo, y
- optimícelo aún más para obtener un algoritmo de tiempo de ejecución O(√n).
Por todo esto y más, empecemos.
Tabla de contenido
¿Qué es un número primo?
Comencemos repasando los conceptos básicos de los números primos.
En teoría de números, se dice que un número natural n es principal si tiene exactamente dos divisores: el 1 y el propio número (n). Recuerda de las matemáticas de tu escuela: se dice que un número i es un factor del número n, si i divide n en partes iguales. ✅
La siguiente tabla enumera algunos números, todos sus factores y si son primos.
nFactores¿Es primo?11No21, 2Sí31, 3Sí41, 2, 4No71, 7Sí151, 3, 5, 15No
De la tabla anterior, podemos anotar lo siguiente:
- 2 es el número primo más pequeño.
- 1 es un factor de cada número.
- Todo número n es factor de sí mismo.
Entonces 1 y n son factores triviales para cualquier número n. Y un número primo no debe tener más factores que estos dos.
Esto significa que cuando pasas de 2 a n – 1, no deberías poder encontrar un factor no trivial que divida n sin resto.
Algoritmo O(n) para verificar si un número es primo en Python
En esta sección, formalicemos el enfoque anterior en una función de Python.
Puede recorrer todos los números del 2 al n – 1 usando el objeto range() en Python.
En Python, range(start, stop, step) devuelve un objeto de rango. Luego puede iterar sobre el objeto de rango para obtener una secuencia desde el inicio hasta la parada -1 en pasos de paso.
Dado que necesitamos el conjunto de enteros de 2 a n-1, podemos especificar range(2, n) y usarlo junto con for loop.
Esto es lo que nos gustaría hacer:
- Si encuentra un número que divide a n de manera uniforme sin resto, puede concluir de inmediato que el número no es primo.
- Si ha recorrido todo el rango de números desde 2 hasta n – 1 sin encontrar un número que divida n de manera uniforme, entonces el número es primo.
Función de Python para verificar el número primo
Usando lo anterior, podemos continuar y definir la función is_prime() de la siguiente manera.
def is_prime(n):
for i in range(2,n):
if (n%i) == 0:
return False
return True
Analicemos ahora la definición de función anterior.
- La función anterior is_prime() toma un entero positivo n como argumento.
- Si encuentra un factor en el rango especificado de (2, n-1), la función devuelve Falso, ya que el número no es primo.
- Y devuelve True si recorre todo el ciclo sin encontrar un factor.
A continuación, llamemos a la función con argumentos y verifiquemos si la salida es correcta.
is_prime(2) # True is_prime(8) # False is_prime(9) # False is_prime(11) # True
En el resultado anterior, ve que 2 y 11 son primos (la función devuelve True). Y 8 y 9 no son primos (la función devuelve Falso).
Cómo optimizar la función de Python is_prime()
Podemos hacer una pequeña optimización aquí. Observe la lista de factores en la siguiente tabla.
NúmeroFactores61, 2, 3, 6101, 2, 5, 10181, 2, 3, 6, 9, 18
Bien, podemos ver que el único factor de n que es mayor que n/2 es el mismo n.
Entonces, esto significa que no tiene que recorrer todo el ciclo hasta n – 1. En su lugar, puede ejecutar el ciclo solo hasta n/2.
Si no encuentra un factor no trivial hasta n/2, tampoco podrá encontrar uno más allá de n/2.
Ahora modifiquemos la función is_prime() para verificar los factores en el rango (2, n/2)
def is_prime(n):
for i in range(2,int(n/2)):
if (n%i) == 0:
return False
return True
Avancemos y verifiquemos la salida a través de algunas llamadas a funciones.
is_prime(9) # False is_prime(11) # True
Aunque parezca que lo hemos optimizado, este algoritmo no es más eficiente que el anterior en términos de complejidad del tiempo de ejecución. De hecho, ambos tienen una complejidad de tiempo de ejecución O(n): proporcional al valor de n o lineal en n.
¿Podemos hacerlo mejor? ¡Si podemos!
▶️ Continúe con la siguiente sección para determinar cómo mejorar la complejidad del tiempo para las pruebas de números primos.
Algoritmo O(√n) para verificar el número primo en Python
Sucede que los factores de un número se presentan en pares.
Si a es un factor del número n, entonces también existe un factor b tal que axb = n, o simplemente, ab = n.
Verifiquemos esto a través de un ejemplo.
La siguiente tabla muestra los factores del número 18 que ocurren en pares. Puede verificar lo mismo para algunos números más si lo desea.
Además, tenga en cuenta que √18 es aproximadamente 4,24.
Y en los factores que ocurren en pares (a, b), puedes ver que si a es menor que 4.24, entonces b es mayor que 4.24—en este ejemplo, (2, 18) y (3, 6).
Factores de 18 en pares
La siguiente figura muestra los factores de 18 trazados en la recta numérica.
Si el número n resulta ser un cuadrado perfecto, tendrás a = b = √n como uno de los factores.
▶️ Mira los factores de 36 en la siguiente tabla. Como 36 es un cuadrado perfecto, a = b = 6 es uno de los factores. Para todos los demás pares de factores (a, b), a < 6 yb > 6 se cumple.
Factores de 36 en pares
Resumiendo, tenemos lo siguiente:
- Todo número n se puede escribir como n = axb
- Si n es un cuadrado perfecto, entonces a = b = √n.
- Y si a < b, entonces, a < √n y b > √n.
- De lo contrario, si a > b, entonces a > √n y b < √n.
Entonces, en lugar de recorrer todos los enteros hasta n/2, puede optar por ejecutar hasta √n. Y esto es mucho más eficiente que nuestro enfoque anterior.
Cómo modificar el algoritmo is_prime() a O(√n)
Procedamos a optimizar la función para buscar números primos en Python.
import math
def is_prime(n):
for i in range(2,int(math.sqrt(n))+1):
if (n%i) == 0:
return False
return True
Ahora, analicemos la definición de función anterior:
- Para calcular la raíz cuadrada de un número, importemos el módulo matemático integrado de Python y usemos la función math.sqrt().
- Como n puede no ser un cuadrado perfecto, tendremos que convertirlo en un número entero. Use int(var) para convertir var en un int.
- Para asegurarnos de que realmente estamos verificando hasta √n, agregamos un más uno ya que la función range() excluye el punto final del rango de manera predeterminada.
La siguiente celda de código verifica que nuestra función is_prime() funciona correctamente.
is_prime(8) # False is_prime(15) # False is_prime(23) # True
En la siguiente sección, vamos a crear algunas gráficas simples para entender O(n) y O(√n) visualmente.
Comparando O(n) y O(√n) Visualmente
▶️ Ejecute el siguiente fragmento de código en un entorno de cuaderno Jupyter de su elección.
import numpy as np
import seaborn as sns
import pandas as pd
n = 20
x = np.arange(n)
y1 = np.sqrt(x)
y2 = x
df = pd.DataFrame({"O(√n)":y1,"O(n)":y2})
sns.set_theme()
sns.lineplot(data = df)
El fragmento anterior muestra cómo puede trazar las curvas para n y √n para un rango de valores.
- Usamos la función NumPy arange() para crear una matriz de números.
- Y luego, recopilamos los valores de n y √n hasta, pero sin incluir 20, en un Marco de datos de pandas.
- A continuación, graficamos usando diagrama lineal de seaborn() función.
De la siguiente gráfica, vemos que √n es significativamente menor que n.
Ahora aumentemos el rango hasta 2000 y repitamos los mismos pasos anteriores.
import numpy as np
import seaborn as sns
import pandas as pd
n = 2000
x = np.arange(n)
y1 = np.sqrt(x)
y2 = x
df = pd.DataFrame({"O(√n)":y1,"O(n)":y2})
sns.set_theme()
sns.lineplot(data = df)
De la gráfica anterior, puede inferir que el algoritmo O(√n) es significativamente más rápido cuando está probando si un número grande es primo.
Aquí hay un ejemplo rápido: 2377 es un número primo, ¡compruébalo! 😀
Mientras que el enfoque O(n) tomará el orden de 2000 pasos, el algoritmo O(√n) puede ayudar a llegar a la respuesta en solo 49 pasos.✅
Conclusión
⏳ Y es hora de un resumen rápido.
- Para verificar si un número es primo, el enfoque ingenuo es recorrer todos los números en el rango (2, n-1). Si no encuentra un factor que divida a n, entonces n es primo.
- Como el único factor de n mayor que n/2 es n mismo, puede optar por correr solo hasta n/2.
- Ambos enfoques anteriores tienen una complejidad temporal de O(n).
- Como los factores de un número se presentan en pares, solo puede correr hasta √n. Este algoritmo es mucho más rápido que O(n). Y la ganancia es apreciable al comprobar si un número grande es primo o no.
Espero que entiendas cómo verificar si un número es primo en Python. Como siguiente paso, puede consultar nuestro tutorial sobre programas Python en operaciones con cadenas, donde aprenderá a verificar si las cadenas son palíndromos, anagramas y más.
Nos vemos en otro tutorial. Hasta entonces, ¡feliz codificación! 👩🏽💻