もしあなたがプログラマだったら、プログラムを書いて10兆までの素数のリストを作ってみてほしい。情報システムの開発に携わる人であれば、10兆までの素数のリストを出力するシステムの見積もりを考えてみてほしい。費用はどれくらいかかるか、納期はどれくらいか、あなたはどんな答を出すだろうか。仕様書はうまく書けるだろうか。

図1●素数を探索するプログラム
図1●素数を探索するプログラム

 記者がこんなことをいうのは、自分で10兆までの素数のリストを作ってみて、とても面白かったからだ。図1のプログラムを書いて出力が成功するまで約2週間、夢いっぱいの楽しいひとときを過ごせた。予期せぬ問題も発生したけれど、最後にはコンピュータがまだまだ発展する可能性を持つと感じられた。素数のリストを作る演習は、プログラミングと情報システムにおける有益な演習の一つである。

アルゴリズムの有効性が納得できる

図2●100以下の素数を表示するコードの例(Visual Basic 2010)
図2●100以下の素数を表示するコードの例(Visual Basic 2010)

 この演習の面白い点は、まずアルゴリズムの有効性を納得できる点だ。素数(prime)は「1とそれ自体以外で割り切れない数」であり、それを最も単純な形で判別するには、ある数を、それより小さい数でひたすら割ってみればよい。図2は100以下の素数を得るVisual Basic 2010のコード例だ。これで「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」という25個の素数を得られる。

 ただ、図2のプログラムは、探索範囲が大きくなると困ったことになる。処理時間が長く、人間が待ち切れないのだ。

図3●エラトステネスのふるいの実装例
図3●エラトステネスのふるいの実装例

 紀元前にはエラトステネスという偉人がいて、効率的に素数を探索するアルゴリズムを考え出した(エラトステネスのふるい)。例えば、10以下の素数が「2 3 5 7」であることがわかっているとする。それならば、100以下の素数を得るには、100以下の数のうち、2の倍数を素数でないとし、3の倍数を素数でないとし、5の倍数を素数でないとし、7の倍数を素数でないとすると、残ったものが素数であるというのである。このアルゴリズムを使って、図2と同様の出力を得るコードが図3だ。100以下で探すくらいだと処理時間にほとんど差はないが、探索範囲を広げる際には、エラトステネスのふるいが絶大な威力を発揮する。

 ここで得られる教訓は、無手勝流でやってもできないことがある、ということ。先人が考案した手法を学ぶことは大切である。

32ビット整数のオーバーフロー

 次の面白さは、大きな出力結果に対処することだ。図2と図3では出力結果を文字列型(String)の変数に連結しているが、この方法では10億まで探索すると現実的な時間では終わらない。10億までの素数は(私が計算したところでは)5084万7534個あり、それをシンプルなテキストファイルにすると527Mバイトの大きさになる。この大きな出力をどう扱うか、プログラマの基本的な技能が試される。

 次に直面するのが32ビット整数のオーバーフローだ。現在広く使われている32ビット整数は、符号付きでは上限が21億くらいだし、符号なしでも42億くらい。図2と図3では符号付き32ビット整数型であるIntegerを無造作に使っているが、探索範囲を広げるとそれではうまくいかない。適切なところに64ビット整数を使えばいいのだが、すべてを64ビット整数にするのもシステム資源の浪費になったり、処理時間を増大させたりする。オーバーフローを経験することは昔より少なくなったが、これもやはりプログラマにとって、基本的な技能を試される局面と言えるだろう。

必要なハードウエアは何か?

 実は今回、記者はハードウエアの増強が必要なのではないかとワクワクしていた。6コアのCPUを買おうかなあ、それとも4Gバイトのメモリーモジュールを6個買って24Gバイトにするかなぁ、などと財布と相談もせずにウキウキしていたのである。

 しかし、100億くらいまで探索してみたところ、問題は出力結果を格納するハードディスクだとわかってきた。10億までの探索で500Mバイト、100億ではその10倍の5Gバイトが必要である(素数の出現確率は意外と減らない)。単純に計算すると、1000億までで50Gバイト、1兆で500Gバイト、10兆で5Tバイトという見積もりだ。

 2Tバイトのハードディスクを3台買ってこようかとも考えたが、結局お金のかからない方法ということで、出力結果を圧縮してZIPファイルにすることに決めた。それでも、10兆までで約500Gバイトのディスク容量を消費する。もちろん、圧縮をすることで処理時間は長くなった。

この先は会員の登録が必要です。有料会員(月額プラン)は初月無料!

日経 xTECHには有料記事(有料会員向けまたは定期購読者向け)、無料記事(登録会員向け)、フリー記事(誰でも閲覧可能)があります。有料記事でも、登録会員向け配信期間は登録会員への登録が必要な場合があります。有料会員と登録会員に関するFAQはこちら