Python で素数列挙

際限なく素数を出力し続ける Python のジェネレータについて説明します。

Python の itertools ライブラリの count 関数と、シンプルな再帰を利用して非常にコンパクトに実装することができます。

次に示すコードを見てみましょう。

from itertools import count

def prime():
  def sieve(ints):
    i = next(ints)
    yield i
    for n in sieve(k for k in ints if k % i != 0):
      yield n
  return sieve(count(2))

このコードの核心部分は、エラトステネスの篩（ふるい）という古代ギリシャの素数列挙アルゴリズムを利用した prime 関数です。

まず、Python 標準ライブラリの itertools から count をインポートします。次に、prime という関数を作ります。

この関数の中に、途切れることなく整数を出力し続けるジェネレーター関数 sieve が定義されています。このジェネレーター関数は、整数列（この場合は 2 から始まる整数列）を引数とし、コルーチンのように振舞います。

sieve 関数の中で、最初に次の整数を取り出して i に保存します。i は素数であり、出力するべき値です。それから、その整数で割り切れない数のみを出力するジェネレータ k for k in ints if k % i != 0 を作成します。

そして、そのジェネレーターを再び sieve 関数に渡すことで、sieve 関数は再帰的に呼び出されることになります。ここで出力されるすべての数は、前のすべての素数で割り切れない素数になります。

これらすべてを組み合わせると、prime 関数は素数を無限に出力できるイテレータを返します。

なお、このコードは真の無限シーケンスを生成しますので、利用の際は注意が必要です。例えば、全ての素数を列挙しようとすると、その操作は永遠に終わらないのでプログラムが停止することはありません。