Un tamiz rápido de números primos en Python

He estado pasando por la generación de números primos en python utilizando el tamiz de Eratóstenes y las soluciones que las personas ofrecen como una opción relativamente rápida, como las que figuran en algunas de las respuestas a una pregunta sobre cómo optimizar la generación de números primos en python , no son sencillas. Implementación simple que tengo aquí compite con ellos en eficiencia. Mi implementación se da a continuación.

def sieve_for_primes_to(n): size = n//2 sieve = [1]*size limit = int(n**0.5) for i in range(1,limit): if sieve[i]: val = 2*i+1 tmp = ((size-1) - i)//val sieve[i+val::val] = [0]*tmp return sieve print [2] + [i*2+1 for i, v in enumerate(sieve_for_primes_to(10000000)) if v and i>0] 

Tiempo de ejecución de las devoluciones

 python -m timeit -n10 -s "import euler" "euler.sieve_for_primes_to(1000000)" 10 loops, best of 3: 19.5 msec per loop 

Si bien el método descrito en la respuesta a la pregunta anterior como el más rápido del libro de recetas de python se presenta a continuación.

 import itertools def erat2( ): D = { } yield 2 for q in itertools.islice(itertools.count(3), 0, None, 2): p = D.pop(q, None) if p is None: D[q*q] = q yield q else: x = p + q while x in D or not (x&1): x += p D[x] = p def get_primes_erat(n): return list(itertools.takewhile(lambda p: p<n, erat2())) 

Cuando se ejecuta da

 python -m timeit -n10 -s "import euler" "euler.get_primes_erat(1000000)" 10 loops, best of 3: 697 msec per loop 

Mi pregunta es ¿por qué las personas mencionan lo anterior en el libro de cocina que es relativamente complejo como el generador ideal ideal?

    Transformé su código para que se ajustara al script de comparación de tamices principales de @unutbu en la forma más rápida de enumerar todos los números primos debajo de N de la siguiente manera:

     def sieve_for_primes_to(n): size = n//2 sieve = [1]*size limit = int(n**0.5) for i in range(1,limit): if sieve[i]: val = 2*i+1 tmp = ((size-1) - i)//val sieve[i+val::val] = [0]*tmp return [2] + [i*2+1 for i, v in enumerate(sieve) if v and i>0] 

    En mi MBPro i7, el script es rápido calculando todos los números primos <1000000 pero en realidad 1,5 veces más lento que rwh_primes2, rwh_primes1 (1.2), rwh_primes (1.19) y primeSieveSeq (1.12) (@andreasbriese al final de la página).

    Solo debe usar la variante “pospuesta” de ese algoritmo . Comparando su prueba de código ejecute hasta 10 y 20 millones de límite superior, como

     ... print(len( [2] + [i*2+1 for i, v in enumerate(sieve_for_primes_to(10000000)) if v and i>0])) 

    con el otro, ejecute en las cifras correspondientes de 664579 y 1270607 primos para producir, como

     ... print( list( islice( (p for p in postponed_sieve() ), n-1, n+1))) 

    muestra su código ejecutándose “solo” 3.1x … 3.3x veces más rápido. 🙂 No 36 veces más rápido, como lo demuestran los tiempos por alguna razón.

    No creo que nadie haya afirmado que sea un generador principal “ideal”, solo que es conceptualmente limpio y claro. Todas estas funciones de primera generación son realmente juguetes, lo real es trabajar con números muy grandes, usando algoritmos completamente diferentes de todos modos.

    Aquí, en el rango bajo, lo que importa es la complejidad temporal del algoritmo, que debería estar alrededor de ~ n^(1+a) , a < 0.1...0.2 órdenes empíricos de crecimiento , que ambos parecen ser en verdad. Tener un generador de juguetes con ~ n^1.5 o incluso ~ n^2 órdenes de crecimiento no es nada divertido para jugar.