Obtener lista de números primos



Versión: 2.x, 3.x.

¿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.

Criba de Eratóstenes

(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. Compliando 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



Deja un comentario