è questo generatore di primoni pythonic

Question

È il seguente codice per la generazione di numeri primi 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) 

nota che il prossimo (next_p) finirà per lanciare un errore StopIteration che finisce in qualche modo i get_primes funzione. È così male?

Si noti inoltre che next_p è un generatore che esegue l'iterazione sui numeri primi, tuttavia i primi vengono modificati durante l'iterazione. È quello stile cattivo?

aggiungendo la seguente istruzione if ottiene sotto 0,25 secondi per il primo milione di numeri primi:

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

Answer 1

Non è male che next(next_p) genera un errore StopIteration - che è quello che un generatore di sempre fa quando si esaurisce di articoli !

Cambiare la lunghezza di un elenco mentre si scorre su di esso è una cattiva idea. Ma non c'è niente di sbagliato semplicemente cambiando il contenuto. Nel complesso, penso che questo sia un po 'elegante, se di base, seive.

Una piccola osservazione: quando "estrai" i multipli dei numeri primi, troverai, se ci penserai un po ', che non devi iniziare con p * 2. Puoi saltare a p ** 2.

Answer 2

Non c'è niente di sbagliato con lo StopIteration, che è il comportamento previsto per i generatori.

direi che questa implementazione è più divinatorio (non necessariamente più efficiente):

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 per me significa chiaro, conciso, leggibile, e utilizzando i punti di forza del linguaggio. Mentre posso vedere che la tua implementazione è una sorta di setaccio, so solo che da un'esperienza precedente con quel tipo di algoritmi. L'implementazione di cui sopra posso leggere direttamente come un test diretto di divisibilità.

---

Nota: c'è una differenza minore nell'interfaccia, l'implementazione sarebbe resa primi < = n mentre la mia realizzazione produrrebbe numeri primi < n. Ovviamente questo può essere cambiato facilmente e banalmente (basta cambiare n a n + 1 nel corpo della funzione), ma sento che è più pitonico generare numeri primi, ma non includere n per essere più coerenti con il modo, per dire , range() opere integrate.

---

EDIT: JUST FOR FUN

Ecco un almeno pythonic implementazione, e probabilmente abbastanza inefficiente troppo :)

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) 

ho questa chiamata il meno divinatorio perché ti staresti grattando la testa per qualche giorno per capire come funziona se prima non avevi visto questo trucco !!

Answer 3

Ecco un'altra soluzione un po 'pitonica motivata da @wim, tuttavia è possibile vederlo leggermente più lento del primo metodo.

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"