Criba de Eratóstenes - Encontrar números primos Python
Sólo para aclarar, este no es un problema de tarea :)
Quería encontrar números primos para una aplicación matemática que estoy construyendo y encontré el enfoque del Tamiz de Eratóstenes .
He escrito una implementación en Python. Pero es terriblemente lento. Por ejemplo, si quiero encontrar todos los números primos menores de 2 millones. Tarda > 20 minutos. (Lo detuve en este punto). ¿Cómo puedo acelerar esto?
def primes_sieve(limit):
limitn = limit+1
primes = range(2, limitn)
for i in primes:
factors = range(i, limitn, i)
for f in factors[1:]:
if f in primes:
primes.remove(f)
return primes
print primes_sieve(2000)
ACTUALIZACIÓN: Terminé haciendo un perfil de este código y descubrí que se dedicó bastante tiempo a eliminar un elemento de la lista. Bastante comprensible considerando que tiene que recorrer toda la lista (en el peor de los casos) para encontrar el elemento y luego eliminarlo y luego reajustar la lista (¿tal vez continúe alguna copia?). De todos modos, descarté la lista para el diccionario. Mi nueva implementación -
def primes_sieve1(limit):
limitn = limit+1
primes = dict()
for i in range(2, limitn): primes[i] = True
for i in primes:
factors = range(i,limitn, i)
for f in factors[1:]:
primes[f] = False
return [i for i in primes if primes[i]==True]
print primes_sieve1(2000000)
No estás implementando del todo el algoritmo correcto:
En su primer ejemplo, primes_sieveno mantiene una lista de indicadores de primalidad para activar/desarmar (como en el algoritmo), sino que cambia el tamaño de una lista de números enteros continuamente, lo cual es muy costoso: eliminar un elemento de una lista requiere cambiar todos los elementos posteriores abajo por uno.
En el segundo ejemplo, primes_sieve1mantiene un diccionario de indicadores de primalidad, lo cual es un paso en la dirección correcta, pero itera sobre el diccionario en un orden indefinido y tacha de manera redundante factores de factores (en lugar de solo factores de números primos, como en el algoritmo ). Puede solucionar este problema ordenando las claves y omitiendo los números no primos (lo que ya lo hace un orden de magnitud más rápido), pero sigue siendo mucho más eficiente usar una lista directamente.
El algoritmo correcto (con una lista en lugar de un diccionario) se parece a:
def primes_sieve2(limit):
a = [True] * limit # Initialize the primality list
a[0] = a[1] = False
for (i, isprime) in enumerate(a):
if isprime:
yield i
for n in range(i*i, limit, i): # Mark factors non-prime
a[n] = False
(Tenga en cuenta que esto también incluye la optimización algorítmica de comenzar el marcado no primo en el cuadrado del primo ( i*i) en lugar de su doble).
def eratosthenes(n):
multiples = []
for i in range(2, n+1):
if i not in multiples:
print (i)
for j in range(i*i, n+1, i):
multiples.append(j)
eratosthenes(100)
