Tamiz de Eratóstenes – Primes entre X y N

Encontré esta implementación altamente optimizada del Tamiz de Eratóstenes para Python en Stack Overflow. Tengo una idea aproximada de lo que está haciendo, pero debo admitir que los detalles de su funcionamiento me eluden.

Todavía me gustaría usarlo para un pequeño proyecto (sé que hay bibliotecas para hacer esto, pero me gustaría usar esta función).

Aquí está el original:

''' Sieve of Eratosthenes Implementation by Robert William Hanks https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n/3035188 ''' def sieve(n): """Return an array of the primes below n.""" prime = numpy.ones(n//3 + (n%6==2), dtype=numpy.bool) for i in range(3, int(n**.5) + 1, 3): if prime[i // 3]: p = (i + 1) | 1 prime[ p*p//3 ::2*p] = False prime[p*(p-2*(i&1)+4)//3::2*p] = False result = (3 * prime.nonzero()[0] + 1) | 1 result[0] = 3 return numpy.r_[2,result] 

Lo que estoy tratando de lograr es modificarlo para que devuelva todos los primos debajo de n comenzando en x para que:

 primes = sieve(50, 100) 

devolvería números primos entre 50 y 100. Esto me pareció bastante fácil, intenté reemplazar estas dos líneas:

 def sieve(x, n): ... for i in range(x, int(n**.5) + 1, 3): ... 

¡Pero por una razón que no puedo explicar, el valor de x en lo anterior no tiene influencia en la matriz numpy devuelta!

¿Cómo puedo modificar el sieve() para devolver solo primos entre x y n

La implementación que tomó prestada puede comenzar en 3 porque reemplaza el tamizado de los múltiplos de 2 simplemente saltándose todos los números pares; de eso se tratan los 2*… que aparecen varias veces en el código. El hecho de que 3 sea la próxima prima también está codificado en todo el lugar, pero ignoremos eso por el momento, porque si no puedes superar la carcasa especial de 2, la carcasa especial de 3 no importa .

Saltar números pares es un caso especial de una “rueda”. Puedes omitir los múltiplos de tamizado de 2 incrementando siempre en 2; puede omitir los múltiplos de tamizado de 2 y 3 incrementando alternativamente en 2 y 4; puede omitir los múltiplos de tamizado de 2, 3, 5 y 7 incrementando alternativamente en 2, 4, 2, 4, 6, 2, 6, … (hay 48 números en la secuencia), y así sucesivamente. Entonces, puedes extender este código al encontrar primero todos los números primos hasta x , luego construir una rueda y luego usar esa rueda para encontrar todos los números primos entre x y n .

Pero eso está agregando mucha complejidad. Y una vez que llega más allá de 7, el costo (tanto en el tiempo como en el espacio para almacenar la rueda) desborda los ahorros. Y si todo tu objective no es encontrar los números primos antes de x , encontrar los números primos antes de x para que no tengas que encontrarlos parece un poco tonto. 🙂

Lo más sencillo es encontrar todos los números primos hasta n y tirar los que están debajo de x . Lo que puedes hacer con un cambio trivial al final:

 primes = numpy.r_[2,result] return primes[primes>=x] 

O por supuesto, hay maneras de hacer esto sin perder el almacenamiento para esos primos iniciales que va a tirar. Sería un poco complicado trabajar en este algoritmo (probablemente querría construir la matriz en secciones, luego eliminar cada sección que sea completamente < x medida que avanza, luego astackr todas las secciones restantes); sería mucho más fácil usar una implementación diferente del algoritmo que no está diseñada para la velocidad y la simplicidad en el espacio ...

Y, por supuesto, hay diferentes algoritmos de búsqueda de primos que no requieren enumerar todos los números primos hasta x en primer lugar. Pero si quieres usar esta implementación de este algoritmo, eso no importa.

Ya que ahora estás interesado en buscar otros algoritmos u otras implementaciones, prueba este. No usa numpy, pero es bastante rápido. He intentado algunas variaciones en este tema, incluido el uso de conjuntos y el cálculo previo de una tabla de números primos bajos, pero todos fueron más lentos que este.

 #! /usr/bin/env python ''' Prime range sieve. Written by PM 2Ring 2014.10.15 For range(0, 30000000) this is actually _faster_ than the plain Eratosthenes sieve in sieve3.py !!! ''' import sys def potential_primes(): ''' Make a generator for 2, 3, 5, & thence all numbers coprime to 30 ''' s = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29) for i in s: yield i s = (1,) + s[3:] j = 30 while True: for i in s: yield j + i j += 30 def range_sieve(lo, hi): ''' Create a list of all primes in the range(lo, hi) ''' #Mark all numbers as prime primes = [True] * (hi - lo) #Eliminate 0 and 1, if necessary for i in range(lo, min(2, hi)): primes[i - lo] = False ihi = int(hi ** 0.5) for i in potential_primes(): if i > ihi: break #Find first multiple of i: i >= i*i and i >= lo ilo = max(i, 1 + (lo - 1) // i ) * i #Determine how many multiples of i >= ilo are in range n = 1 + (hi - ilo - 1) // i #Mark them as composite primes[ilo - lo : : i] = n * [False] return [i for i,v in enumerate(primes, lo) if v] def main(): lo = int(sys.argv[1]) if len(sys.argv) > 1 else 0 hi = int(sys.argv[2]) if len(sys.argv) > 2 else lo + 30 #print lo, hi primes = range_sieve(lo, hi) #print len(primes) print primes #print primes[:10], primes[-10:] if __name__ == '__main__': main() 

Y aquí hay un enlace al tamiz de Eratóstenes que mencioné en la cadena de documentación, en caso de que quiera comparar este progtwig con ese.

Podría mejorar esto un poco #Eliminate 0 and 1, if necessary el bucle en #Eliminate 0 and 1, if necessary . Y supongo que podría ser un poco más rápido si evitaras mirar números pares; Ciertamente usaría menos memoria. Pero entonces tendrías que manejar los casos cuando 2 estaba dentro del rango, y me imagino que cuantas menos pruebas tengas, más rápido funcionará esto.


Aquí hay una pequeña mejora en ese código: reemplazar

  #Mark all numbers as prime primes = [True] * (hi - lo) #Eliminate 0 and 1, if necessary for i in range(lo, min(2, hi)): primes[i - lo] = False 

con

  #Eliminate 0 and 1, if necessary lo = max(2, lo) #Mark all numbers as prime primes = [True] * (hi - lo) 

Sin embargo, la forma original puede ser preferible si desea devolver la lista de bool simples en lugar de realizar la enumerate para crear una lista de enteros: la lista de bool es más útil para probar si un número dado es primo; OTOH, la enumerate podría usarse para construir un conjunto en lugar de una lista.