es este generador de primos pythonic

Question

¿El siguiente código para generar primos es pythonic?

def get_primes(n): 
    primes=[False,False]+[True]*(n-1) 
    next_p=(i for i,j in enumerate(primes) if j) 
    while True: 
     p=next(next_p) 
     yield p 
     primes[p*p::p]=[False]*((n-p*p)//p+1) 

Tenga en cuenta que el próximo (next_p) finalmente lanzar un error StopIteration que de alguna manera termina la función get_primes. ¿Es tan malo?

También tenga en cuenta que next_p es un generador que itera sobre primos, sin embargo los primos cambian durante la iteración. ¿Es ese mal estilo?

agregando la siguiente instrucción if pone debajo de 0,25 segundos para el primer millón de números primos:

if p*p<=n: 
    primes[p*p::p]=[False]*((n-p*p)//p+1) 

Answer 1

No es malo que next(next_p) genera un error StopIteration - eso es lo que un generador siempre cuando se queda sin elementos de !

Cambiar la longitud de una lista mientras se itera sobre ella es una mala idea. Pero no hay nada malo con simplemente cambiar los contenidos. En general, creo que esto es bastante elegante, si es básico, seive.

Una pequeña observación: cuando "tacha" los múltiplos de números primos, encontrará, si lo piensa por un momento, que no tiene que empezar por p * 2. Puede saltear adelante al p ** 2.

Answer 2

No hay nada de malo en el StopIteration, de hecho ese es el comportamiento esperado de los generadores.

Yo diría que esta implementación es más Pythonic (no necesariamente más eficiente):

def get_primes(n): 
    """Generates prime numbers < n""" 
    return (x for x in xrange(2,n) if all(x % i for i in xrange(2,x))) 

Pythonic para mí significa clara, concisa y fácil de leer, y el uso de los puntos fuertes de la lengua. Si bien puedo ver que su implementación es una especie de tamiz, solo lo sé por experiencia previa con ese tipo de algoritmos. La implementación anterior puedo leer directamente como una prueba directa de divisibilidad.

---

Nota: hay una diferencia menor en la interfaz, su aplicación sería dió primos < = n mientras que mi aplicación produciría primos < n. Obviamente, esto se puede cambiar de manera fácil y trivial (simplemente cambie n a n + 1 en el cuerpo de la función), pero creo que es más pitónico generar primos hasta-pero-no incluyendo n para ser más consistente con el modo, digamos , range() obras incorporadas.

---

EDITAR: JUST FOR FUN

Aquí es una aplicación Pythonic menos, y probablemente bastante ineficiente también :)

def get_primes(n): 
    import re 
    return (x for x in xrange(2,n) if re.match(r'^1?$|^(11+?)\1+$', '1' * x) is None) 

Yo llamo a esto la menor porque Pythonic ¡te estarías rascando la cabeza por algunos días para descubrir cómo funciona si no has visto este truco antes!

Answer 3

Aquí hay otra solución algo pitonica motivada por @wim, sin embargo puedes ver que es un poco más lenta que el primer método.

def get_primes2(n): 
    primes=[] 
    for i in range(2,n+1): 
     small_primes=(p for p in primes if p*p<=i) 
     if all(i%p for p in small_primes): 
      yield i 
      primes.append(i) 

import timeit 
print(timeit.timeit("list(get_primes(10**5))",number=5,setup="from __main__ import get_primes")/5.0) 
"0.0350940692182945" 
print(timeit.timeit("list(get_primes2(10**5))",number=5,setup="from __main__ import get_primes2")/5.0) 
"8.226938898658908"