Pythonによる素数列の現代的実装法

素数、素数、素数の話で疲れたので閑話。

とは言っても閑話もまた素数のプログラミングである。

疲れた最大の原因はBASICなぞと言う大昔の言語に振り回されたから、に過ぎない。

よって、Pythonで実装してみれば如何にラクか、その実例をお見せしようと思う。

とは言っても、そのまま実装してもクソも面白くない。

従って、「あっ」て驚くだろうテクニックをちょっと紹介してみる。

通常、素数を見つけるプログラミングだと、プログラムのユーザーが、最大値を与えたりしてその最大値に達するリストを返したり、そういうプログラムになると思う。つまり、上限が存在するのだ。

ここでは上限が存在しない、「無限長の素数列」の実装法をご紹介しよう。

通常こういうのはHaskellみたいな、元々「無限長のリスト」を扱える言語に限られた話題だ。遅延評価、と言う言葉を聞いた事があるだろうか。

遅延評価と「無限長のリスト」と言うのは実は密接な関係がある。要するに「無限長が」具現化したモノに対しては、いかに最新機能を備えた言語でも扱う事は出来ない。ただし、具現化する前の「概念」の状態だとどういう長さのモノでも書き表す事が出来る。

これは、プログラミング言語で言うと、「評価」と言うモノと関係がある。通常、関数に引数が与えられた時、まずはその引数が「評価」される。これを先行評価、と呼んだりする。引数が先行評価されて、関数に手渡される。これが通常のプログラミング言語の動作の順番だ。

一方、先に関数が評価されて、その後「必要に応じて」引数が評価される場合、これを遅延評価と呼ぶ。一旦引数の評価は後回しにされるわけだ。一旦引数の評価が後回しにされる以上、ここが無限長の長さでも構わない。必要に応じて引数の先頭から評価されて、あとは無限長の未評価の部分はそのまま残る。無限長から1引いても無限長なんで、なんら影響はない。あとは概念としての「無限長」部分はそこにそのまま存在する。これがHaskellなんかの評価システムになり、場合によると先行評価のプログラミング言語と少々違った動きをすることになる。

とまぁ、大雑把に遅延評価の説明をしてみたわけだが。Pythonは、かなりフツーの言語なので、当然先行評価のプログラミング言語である。ただし、ちと面白い機能がある。ジェネレータと言う機能だ。

厳密に言うとジェネレータは遅延評価ではない。ただし、場合によってはかなり似た動きをする。

まあ、Web検索をすると、Pythonとジェネレータと言うキーワードでPythonにはyieldと言う機能がある、ってのを見つけるだろう。これはreturnに近い動きをするが、近い動きをするが故、かなり混乱してる人たちがいる。

平たく言うと、yieldと言うのは値を返すんだけど、こいつが組み込まれた関数の動きを途中で停止させてその状態のまま保持する機能である。

簡単な例を挙げてみよう。

def integers_starting_from(n):
　while True:
　　yield n
　　n += 1

この関数、integers_starting_fromの引数nにある数を与えたら、繰り返ししてnの値は1づつ増えていく。ただし、中にyieldがあるので、一旦nの値が返されたらそのままの状態で停止する。次に呼び出した時、繰り返しの続きが始まって、nの値が1増える。while構文によって次の繰り返しが始まるが、またもやyieldに動作が止められて、nと言う値が返る。以下繰り返し、である。

要するに、すん止め、である(笑)。出そうなのに出ない(笑)。また始まった、と思ったらすん止め、と言う男だったら地獄状態だな(笑)。これをやるのが峰不二子ばりの悪女、yield、ってこった。

こういうおかしな関数を書くことが出来るのがyieldで、これをPythonではジェネレータと呼ぶのだ。しかも今この時点で分かってるのは、実はこいつ(integers_starting_from)は動作的には無限ループなのである。無限ループなんだけど、途中で動作を止めて途中経過を返してくれる、と。

つまり、言い換えると、

・returnはフツーのプログラミング言語のように、制御を呼び出し側に返す

・yieldはreturnと違い、制御を呼び出し側に返さない。

と捉える事が出来る。しかも無限ループを書いてるのに、一々動作を停止してくれて、途中結果を「見せて」くれるわけだ。

そう、ジェネレータは本質的には「無限ループ」の関数なのだ。無限ループだけど一々立ち止まってくれる。ここが重要。そして、この「無限ループ」を利用すれば、当然無限長の素数列、と言う、いささか胡散臭いブツを記述可能だ、と言う事である。

このyield付き関数、ジェネレータは次のようにして使う。

>>> val = integers_starting_from(1)
>>> val.__next__()
1
>>> val.__next__()
2
>>> val.__next__()
3
>>> val.__next__()
4
>>> val.__next__()
5
>>>

変数valを作って代入して、特殊メソッド__next__()を呼び出す度に、現時点のyieldによる返り値を返してくれる。5回で止めてるが、この後同じ事をやっていけば10だろうが100だろうが、どんどん1づつ返す数が増えていく。

また、ジェネレータはfor文と組み合わせて以下のような事も出来る。

>>> lst = []
>>> for val in integers_starting_from(0):
　　　　if len(lst) == 5:
　　　　　break
　　　　else:
　　　　　lst.append(val)

>>> lst
[0, 1, 2, 3, 4]
>>>

そう、実はPythonには、C言語で言うような繰り返し用の制御構造は無い。Pythonのforはむしろ、データ型に組み込まれたイテレータの動作をスタートさせる為のキーワードである。従って、forは、ジェネレータのような「おかしな関数」に対しても、イテレートしろ、と言う命令を下す事が可能なのである。

と言うわけで、これがyieldとジェネレータの概要である。まぁ、ハッキリ言って、かなり端折った不確かな説明なんだけど、取り敢えずはこれで充分だろう。あとはQiitaにでも寄って色々と見てくれ。

さて、何で「延々と1づつ増える整数列を返す」ようなジェネレータを書いたのか。もちろん「一番簡単だから」ってのもあるんだけど、こいつを利用して素数列を作っちまおう、と言う寸法だ。「無限にある整数列」を対象にすれば「無限にある素数列」が作れる。まぁ、当然だな。

とは言っても、たった2つの関数・・・正確に言うと一つの「またもや」ジェネレータと、一つの判定用関数を書けば済む、と言うちょっとビックリな結果なのだよ。

仕上げを御覧じろ。

def primes():
　yield 2
　for n in integers_starting_from(3):
　　if is_prime(n):
　　　yield n

def is_prime(n):
　for ps in primes():
　　if ps * ps > n:
　　　return True
　　elif n % ps == 0:
return False

これだけだ。これだけで「無限に続く素数列」が入手出来る。

ジェネレータprimesが本体なんだけど、yieldが2つ使ってある。さっきも書いた通り、yieldは関数の動作を途中で止める。従って最初に呼び出されて2を返したら、その状態のままそこでストップするわけだ。次に呼び出された時は、次の行から始まり、またもや無限ループに突入する。そしてもはや2がどーの、ってトコには戻らない。永遠に宇宙の彼方だ。

その無限ループ。forは先程書いたintegers_starting_fromに引数3を与えて呼び出している。これで3から順繰りに整数が生成されるわけだ。まさしくジェネレータ。そして上限は存在しない。延々と+1された整数を吐き出し続ける。

そしてその吐き出された整数は関数is_primeによって素数なのかテストされる。テストに成功すればyieldで値が返されるが、そうじゃなければまたもやintegers_starting_fromから値がやってきてテストされるのだ。

関数is_primeは試し割り法で素数かどうかチェックする。素数列からまずは最初の素数を持ってきて、そいつの二乗が与えられた数nよりも大きければnは素数、そうじゃない場合、nがその素数で割り切れるかどうかチェックする。当然割り切れた場合は素数ではない。ここまでで判定出来なかった場合、次に大きな素数を持ってきて同様の事をテストする。

さて、実はこの関数、インチキがある。今軽く

「素数列からまずは最初の素数を持ってきて」

と書いたが、その素数列を求める為にプログラムを書いてたのではなかったか。

その通り。

実はここで判定に使ってる素数列はさっき書いたジェネレータ、primesである。

要するに、primesはis_primeを使って素数を判定してるのに、is_primeはprimesを使って素数を判定してるのである。つまり相互再帰してる、ってのがそのインチキのあらましだ。しかし不思議な事にこれで上手く動く、のである。

秘訣は、primesで最初にyield 2してる事だ。我々の前提知識では2は問答無用に素数であるが、コンピュータ及びプログラミング言語は2が素数どうかは知らない。そしてここでは、この2は素数判定と全く関係なく返ってくる。これは我々が「2は素数だ」と予め知っているから仕込んでるわけだ。

なんで最初っからintegers_starting_from(2)にしないでintegers_starting_from(3)にしたのか、ってのが実はそれが理由。ここをintegers_starting_from(2)してプログラム上の素数判定に任せると無限ループに陥り、相互再帰なんで、Pythonだとスタックを消費してエラーで停止してしまう。

# ダメなprimesの例
def primes():
　for n in integers_starting_from(2):
　　if is_prime(n):
　　　yield n

実は2、3と素数が並んでて、最初に明示的に2だけが返るお陰で、3の素数判定の場合、相互再帰してても確実に最初のテストを通過する(何故なら予め2は無条件に素数だと分かってるから)、と言う保証がここで得られるのだ。そうなったら素数数は総数2個を確保出来、以降のテストを円滑に進める事が出来る。これがintegers_starting_from(2)だと素数テストの相互再帰が上手く行かないのにintegers_starting_from(3)だと上手く行く理由である。「自動化するまで」には準備が必要で、その最小限の条件ってのは「確実に2が素数だ(と我々が保証する)」と言う事なのだ(言い換えるとこれが初期条件だ、と言う事である)。

と言うわけで、クソシチメンド臭い、BASICの、しかも上限が厳しい素数を得るプログラムから離れた、Pythonによる現代的な、つまり遅延評価的な素数のプログラミング法は以上である。使い方は、例えば、さきほど見せたようなfor文との組み合わせで、