Cribado de Eratóstenes

El cribado de Eratóstenes es un algoritmo para averiguar todos los números primos menores que un número natural dado. Los números naturales, a diferencia de los enteros, no comprenden los números negativos.

Se considera un número primo el número que tiene dos divisores, el propio número y 1, por tanto, dado que el número 1 sólo tiene un divisor, el primer número primo es el 2.

Con la criba de Eratóstenes se crea una tabla de números desde el 2 hasta el número natural dado y comenzando por el 2, se tachan todos sus múltiplos, el siguiente número no tachado es un número primo y se tachan todos sus múltiplos, así sucesivamente hasta que el cuadrado del siguiente número sea mayor que el número dado.

¿Cómo hacemos esto con Python?

Podemos crear una función y llamarla cribado_eratostenes(n) , esta contendrá él algoritmo. Este ha de comenzar declarando dos variables, una para sumar la cantidad de números primos encontrados y otra donde almacenará una lista de números del 2 hasta el número n dado.

Para continuar recorremos los números de la lista verificando que no sea None (tachado), si lo fuera continua con el siguiente, si el siguiente es un número diferente de None (no tachado) es por tanto primo, así que convierte en None (tacha) los múltiplos del número, hasta el número final dado.

Finalmente devuelve el total y una lista con los números restantes diferentes a None, es decir los números primos que son los no tachados.

Vamos a usar el algoritmo para averiguar los números primos entre 2 y 20, para eso usamos la función: cribado_eratostenes(20) obteniendo dos valores el total de números primos y la lista de números primos como en el ejemplo:

def cribado_eratostenes(n):
    """
    Implementación del Cribado de Eratóstenes
    """
    total=0
    # Creamos una lista con todos los números del 2 al n
    numeros = list(range(2, n+1))
    # Iniciamos el cribado
    for i in numeros:
        # Si el número ya ha sido marcado como no primo, saltamos a la siguiente iteración
        if i is None:
            continue
        # Si el número es primo, marcamos todos sus múltiplos como no primos
        total+=1
        for j in range(i*2, n+1, i):
            numeros[j-2] = None
    # Devolvemos una lista con los números primos encontrados
    return total,[num for num in numeros if num is not None]

# Encontramos los primeros números primos
total,primos = cribado_eratostenes(20)
# Imprimimos los resultados
print(f"Total de números encontrados {total}, números primos {primos}")

Total de números encontrados 8, números primos [2, 3, 5, 7, 11, 13, 17, 19]

¿Y si le decís que averigüe algunos números primos mas?