Tamiz de Eratóstenes en Python

La Criba de Eratóstenes es un algoritmo muy común para sacar los números primos por debajo de un número dado. Este número debe ser inferior a diez millones.

El algoritmo es simple de entender y se implementa con frecuencia en la programación. Este tutorial demostrará la implementación del algoritmo Tamiz de Eratóstenes de Python.

Comencemos por entender primero la lógica detrás de este algoritmo. Primero, escribimos todos los números entre 2 y el número proporcionado Supongamos 50.

Luego tomamos el primer número primo, 2, y marcamos todos los números mayores que su cuadrado y divisibles por 2. Luego repetimos lo mismo con el siguiente número primo, 3.

El mismo procedimiento se realiza hasta que el número primo 7 cuadrado del siguiente al 7 sea 121 y mayor que 50. Después de marcar todos los números, los valores sin marcar son los números primos hasta el 50.

La siguiente figura muestra el resultado final.

Usa el tamiz de Eratóstenes en Python

Primero crearemos una lista del rango requerido. Esta lista marcará True o False para el índice dado.

Inicialmente, la lista contiene todos los elementos como True. Usaremos un bucle anidado para hacer los cambios y marcar las posiciones no principales como Falsas.

Después de esto, almacenaremos las posiciones donde el valor aún es Verdadero en una nueva lista. Esta lista contiene los números primos.

def sieve_of_eratosthenes(val):
    max = val + 1
    lst = [True] * max
    for i in range(2, int(val ** 0.5 + 1)):
        if lst[i]:
            for j in range(i * i, max, i):
                lst[j] = False
    final = []
    for i in range(2, max):
        if lst[i]:
            final.append(i)
    return final


print(sieve_of_eratosthenes(100))

Producción :

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Es posible realizar cambios menores en el código anterior para mejorar la complejidad del tiempo. Por ejemplo, podemos usar conjuntos o diccionarios para filtrar números no primos.

El resultado final se devuelve en una lista, pero use diccionarios o conjuntos mientras marca los números primos y no primos como True o False.

def sieveoferatosthenes_dict(n):
    max = n + 1
    d = dict()
    for i in range(2, max):
        d[i] = True

    for i in d:
        factors = range(i, max, i)
        for f in factors[1:]:
            d[f] = False
    lst = [i for i in d if d[i] == True]
    return lst


print(sieveoferatosthenes_dict(100))

Producción :

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

En el ejemplo anterior, usamos el diccionario d para marcar los valores como True o False para filtrar los números primos. El resultado final es una lista.