はこの素数ジェネレータPythonicです

Question

素数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) 

next（next_p）は、最終的に何らかの方法でget_primesを終了するStopIterationエラーをスローします。それは悪いですか？

また、next_pは素数を反復するジェネレータですが、反復中に素数は変化します。その悪いスタイルですか？

文は最初の100万個の素数のために0.25秒の下でそれを取得する場合、次の追加：

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

Answer 1

next(next_p)がStopIterationエラーをスローすることを悪くはない - それはそれは項目がなくなったときに発電機は常に何をするかです！

リストの反復処理中にリストの長さを変更することは悪い考えです。しかし、単にコンテンツを変更するだけで何も問題はありません。全体的に、私はこれが基本的であればかなりエレガントだと思います。

小規模な観察：素数の倍数を「クロスアウト」すると、少し考えてみると、p * 2で始める必要はありません。 p ** 2に進むことができます。

Answer 2

StopIterationには何も問題はありませんが、実際にはジェネレータの予想される動作です。私はこの実装はもっとニシキヘビ（必ずしも、より効率的）であると言うでしょう

：

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))) 

Python的私には、明確かつ簡潔で読みやすい、および言語の強みを使用することを意味します。あなたの実装はある種のふるいであることがわかりますが、私はその種のアルゴリズムの経験から知っています。上記の実装は、直接的な分裂性テストとして直接読むことができます。

---

注：インタフェースのマイナーな違いがある私の実装では、素数< n個を生じるのに対し、あなたの実装が素数< = Nをもたらすであろう。もちろん、これは簡単かつ自明変更することができます（ちょうど関数本体中のn + 1からnに変更）が、私は言う、アップツーしかし-ないnが途中でより一貫性のあることを含む、素数を生成するために、より多くの神託であると感じ、range()が組み込まれています。

---

EDIT：ちょうど楽しみのため

ここでは少なくとも神託の実装、およびおそらくかなり非効率的である、あまりにも:)

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) 

私はので、少なくともニシキヘビこれを呼び出しますあなたは前にこのトリックを見ていない場合は、それがどのように機能するかを理解するためにいくつかの日のためにあなたの頭を悩まだろう！

Answer 3

@wimが動機づけているもう少し無能な解決策がありますが、最初の方法よりもやや遅いことがわかります。

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"