La Criba de Eratóstenes

Criba de Eratóstenes

Yo ví que no escribí nada sobre teoría, hasta el momento, así aquí está la Criba de Eratóstenes en Python. El objetivo de la Criba de Eratóstenes es encontrar los números primos. Por lo general, la Criba de Eratóstenes es mejor usarla cuando el alcance que está buscando es pequeño. La razón es que la Criba itera sobre los números  varias veces a lo largo del tiempo, por lo tanto, consumiendo memoria y tiempo.

La Criba trabaja comenzando en 2 y buscando hasta ‘n’, por todos múltiplos de 2. Los múltiplos de 2 son rechazados y el siguiente número que no se rechaza está el número primo. Busca los múltiplos del número primo y se rechazam, y se repite. La idea es que el siguiente número no rechazado sea siempre un número primo. También, puede reducirse el tiempo por búsqueda de la raíz cuadrada de ‘n’.

El código puede ser mostrado como:

def criba(n):
    """buscar numeros primas hasta 'n'."""
    a = [False] * 2 + [True] * (n-1) #inicializa una lista de elementos True y False  
    for (i, primo) in enumerate(a):
        if primo:
            for x in range(i*i, n, i):
                a[x] = False
    return [j for (j,k) in enumerate(a) if k == True]

La nota de autor: Jajaja. Mi internet estaba muerto. Le editaré tarde.

Por más información:

Obtener lista de números primos

http://bytesofcode.pythonblogs.com/102_bytesofcode/archive/431_cdigo_en_python_para_hacer_la_criba_de_eratstenes.html

https://es.wikipedia.org/wiki/Criba_de_Erat%C3%B3stenes

(inglés, obtuve el código aquí) https://stackoverflow.com/questions/3939660/sieve-of-eratosthenes-finding-primes-python