La Criba de Eratóstenes
Posted on
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:
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
Deja un comentario