Pythonのジェネレータを使って素数を求める

キミならどう書く 2.0 - ROUND 1 -

Python 2.3から(だったっけな？)導入された「ジェネレータ関数」を使って素数を求めてみましょう。

 >>> def primegen(x=2):        # 素数を返すジェネレータ関数を定義
 ...     while True:
 ...         if not [i for i in range(2,x) if x % i == 0]:
 ...             yield x       # 割りきれる数が見つからなかったらyield
 ...         x += 1
 ... 
 >>> i = primegen()            # イテレータオブジェクトを得る
 >>> while True:
 ...    prime = i.next()       # ジェネレータ関数から次の素数を得る
 ...    if prime > 100: break; # 素数が100を越えたらループを終了
 ...    print prime,           # 素数を表示
 ...  
 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

ジェネレータ関数の面白さを知って頂くことが目的。アルゴリズムは素朴です。

Pythonのジェネレータ関数を使うと，「イテレーション」を手軽に行うことができます。yield文はreturn文のようなもので，関数から値を返します。return文と異なるのは，yieldの後も関数の実行が継続する点です。

whileで100以下に限定していますが，ジェネレータを使うと，計算時間が許す限り無限に素数を生成できます。

あ，インタラクティブシェルを使っていますので，「>>>」や「...」を打ち込む必要はありません:-)。