¿Cómo determinar si un número es primo en Python? En este artículo analizamos y proveemos un método sencillo y eficiente. Si quieres ahorrarte la explicación y simplemente copiar y pegar la función para dicha tarea, el código completo está al final.
El algoritmo
Ahora bien, el proceso para obtener un número primo se divide en dos funciones. La primera tiene como objetivo obtener todos los números primos desde 2 hasta un número natural determinado y retornarlos en una lista. La segunda indica si un número provisto es primo llamando a la función anterior y observando si éste se encuentra en la lista.
Para el primer caso emplearemos el algoritmo conocido como Criba de Eratóstenes, que a pesar de ser formulado hace más de 2000 años es uno de los más eficientes. Veamos qué dice el enlace anterior de Wikipedia sobre el proceso de selección.
Se forma una tabla con todos los números naturales comprendidos entre 2 y n, y se van tachando los números que no son primos de la siguiente manera: Comenzando por el 2, se tachan todos sus múltiplos; comenzando de nuevo, cuando se encuentra un número entero que no ha sido tachado, ese número es declarado primo, y se procede a tachar todos sus múltiplos, así sucesivamente. El proceso termina cuando el cuadrado del mayor número confirmado como primo es mayor que n.
(Clic en la imagen para ver el código de fuente de la animación.)
En base a esta descripción, iremos desarrollando el código de la función y presentándolo de forma ordenada. Para comenzar, definimos la función que obtiene un número natural n al que denominamos max_number (número máximo).
def get_prime_numbers(max_number):
Luego, creamos la tabla (una lista, en nuestro caso) de número naturales entre el 2 y el argumento.
numbers = [True, True] + [True] * (max_number-1)
Un valor verdadero corresponde a un número no tachado, y un valor falso a un número tachado. Para que cada índice de la lista corresponda con el número de la lista, ésta comienza con dos elementos arbitrarios ([True, True]) que ocupan las posiciones 0 y 1.
Seguimos definiendo dos variables. La primera contiene el último número primo obtenido (comenzando por el 2), y la segunda un número múltiplo del anterior.
last_prime_number = 2
i = last_prime_number
Recordamos que el proceso de selección finaliza cuando el cuadrado del último número primo obtenido (last_prime_number) es mayor que el argumento.
while last_prime_number**2 <= max_number:
Una vez dentro del proceso de criba, debemos tachar (es decir, asignar el valor False en la lista) todos los múltiplos del último número primo obtenido.
i += last_prime_number
while i <= max_number:
numbers[i] = False
i += last_prime_number
Realizado esto, debemos repetir este método para el número no tachado inmediatamente siguiente al último número primo obtenido.
j = last_prime_number + 1
while j < max_number:
if numbers[j]:
last_prime_number = j
break
j += 1
i = last_prime_number
Una vez terminado el proceso, los números primos son aquellos pertenecientes a la lista numbers que no estén tachados (que contengan el valor True). Mediante el siguiente código filtramos la lista y retornamos los números primos, recordando que los números 0 y 1 no son tenidos en cuenta.
return [i + 2 for i, not_crossed in enumerate(numbers[2:]) if not_crossed]
Estando ya lista la primera parte, solo nos queda determinar si un determinado número se encuentra en la lista anterior para afirmar que es primo.
def is_prime(n):
return n in get_prime_numbers(n)
¡Ya tenemos listas ambas funciones! Realizamos una prueba:
print(get_prime_numbers(20)) # [2, 3, 5, 7, 11, 13, 17, 19] print(is_prime(3)) # True
Implementación en Cython
Para largos bucles o grandes números la velocidad puede ser un factor importante. Compilando la función get_prime_numbers con Cython y definiendo el tipo de las variables utilizadas podemos incrementar la velocidad del algoritmo entre 7 y 8 veces.
Llamamos a la extensión cprime.pyx y hacemos las pequeñas modificaciones mencionadas anteriormente.
#!/usr/bin/env python
# -*- coding: utf-8 -*-
def get_prime_numbers(int max_number):
cdef int i, j, last_prime_number, not_crossed
numbers = [True, True] + [True] * (max_number-1)
last_prime_number = 2
i = last_prime_number
while last_prime_number**2 <= max_number:
i += last_prime_number
while i <= max_number:
numbers[i] = False
i += last_prime_number
j = last_prime_number + 1
while j < max_number:
if numbers[j]:
last_prime_number = j
break
j += 1
i = last_prime_number
return [i + 2 for i, not_crossed in enumerate(numbers[2:]) if not_crossed]
Creamos el archivo setup.py para compilar.
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from distutils.core import setup
from Cython.Build import cythonize
setup(
name = "CPrime",
ext_modules = cythonize("cprime.pyx"),
)
Y compilamos la extensión ejecutando el siguiente comando.
python setup.py build_ext --inplace
Ahora podemos importar la función de la siguiente forma.
from cprime import get_prime_numbers
Podemos calcular el tiempo de ejecución y comparar ambas funciones con el siguiente código.
#!/usr/bin/env python
# -*- coding: utf-8 -*-
def get_prime_numbers(max_number):
numbers = [True, True] + [True] * (max_number-1)
last_prime_number = 2
i = last_prime_number
while last_prime_number**2 <= max_number:
i += last_prime_number
while i <= max_number:
numbers[i] = False
i += last_prime_number
j = last_prime_number + 1
while j < max_number:
if numbers[j]:
last_prime_number = j
break
j += 1
i = last_prime_number
return [i + 2 for i, not_crossed in enumerate(numbers[2:]) if not_crossed]
if __name__ == "__main__":
import timeit
print("Python", timeit.timeit("get_prime_numbers(20)", number=100000, globals=globals()))
from cprime import get_prime_numbers as get_prime_numbers_fast
print("Cython", timeit.timeit("get_prime_numbers_fast(20)", number=100000, globals=globals()))
El resultado es:
Python 1.1707671845456964
Cython 0.15093119555161216
Código final
Obtener lista de números primos
def get_prime_numbers(max_number):
# Crear una lista que contiene el estado (tachado/no tachado)
# de cada número desde 2 hasta max_number.
numbers = [True, True] + [True] * (max_number-1)
# Se comienza por el 2. Esta variable siempre tiene un
# número primo.
last_prime_number = 2
# Esta variable contiene el número actual en la lista,
# que siempre es un múltiplo de last_prime_number.
i = last_prime_number
# Proceder siempre que el cuadrado de last_prime_number (es decir,
# el último número primo obtenido) sea menor o igual que max_number.
while last_prime_number**2 <= max_number:
# Tachar todos los múltiplos del último número primo obtenido.
i += last_prime_number
while i <= max_number:
numbers[i] = False
i += last_prime_number
# Obtener el número inmediatamente siguiente al último
# número primo obtenido (last_prime_number) que no esté tachado.
j = last_prime_number + 1
while j < max_number:
if numbers[j]:
last_prime_number = j
break
j += 1
i = last_prime_number
# Retornar todas los números de la lista que no están tachados.
return [i + 2 for i, not_crossed in enumerate(numbers[2:]) if not_crossed]
Optimización de velocidad en Cython (de 7 a 8 veces más rápido):
def get_prime_numbers(int max_number):
cdef int i, j, last_prime_number, not_crossed
numbers = [True, True] + [True] * (max_number-1)
last_prime_number = 2
i = last_prime_number
while last_prime_number**2 <= max_number:
i += last_prime_number
while i <= max_number:
numbers[i] = False
i += last_prime_number
j = last_prime_number + 1
while j < max_number:
if numbers[j]:
last_prime_number = j
break
j += 1
i = last_prime_number
return [i + 2 for i, not_crossed in enumerate(numbers[2:]) if not_crossed]
Determinar si un número es primo
# Debe importarse la función anterior.
def is_prime(n):
return n in get_prime_numbers(n)
Ejemplos
>>> get_prime_numbers(70) [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67] >>> is_prime(4) False >>> is_prime(7) True >>> is_prime(20) False >>> is_prime(53) True
Curso online 👨💻
¡Ya lanzamos el curso oficial de Recursos Python en Udemy!
Un curso moderno para aprender Python desde cero con programación orientada a objetos, SQL y tkinter en 2024.
Consultoría 💡
Ofrecemos servicios profesionales de desarrollo y capacitación en Python a personas y empresas. Consultanos por tu proyecto.