« プロジェクトオイラーを遊び倒すガイド(導入編) | メイン | プロジェクトオイラーを遊び倒すガイド(中級編) »

プロジェクトオイラーを遊び倒すガイド(初級編)


前回の導入編では、プロジェクトオイラー(Project Euler)の概要を紹介しました。本記事では、実際にどんなふうに問題を解いていくか、その様子を述べてみようと思います。

それではさっそく問題にトライしてみましょう。本来なら、実際の問題を使うところなのですが、ネタバレはできるだけ書きたくないので、実物を模したオリジナル問題を3つ(初級、中級、上級)作ってみました。これを題材に、プロジェクトオイラーへの取り組み方を見ていきましょう。

初級編はこんな問題です。

【初級問題】 よく知られているように、2は1番目の素数であり、3は2番目、5は3番目、7は4番目の素数である。 n 番目の素数 p に対し、n もまた素数である場合に、p を「素数番目の素数」と呼ぶことにしよう。 3と5は素数番目の素数だが、2と7はそうではない。 100万以下の素数番目の素数の総和を求めよ。

素数をテーマにした問題です。プロジェクトオイラーでは、素数をあつかう問題がとてもよく出されます。

初級編を解いてみよう

さて、この問題はどうすれば解けるでしょうか? ぱっと考える感じ、条件に合う素数をすべて見つけて、順に足し算してやればよさそうです。そこでまずは100万以下の素数をすべて求めて、何番目かを先頭からチェックしていく、というアプローチで進めてみましょう。

100万以下の素数をすべて求めるにはどうすればよいでしょうか? 素数のリストを求めるアルゴリズムとしてよく知られた「エラトステネスのふるい」が有効そうです。これを使って求めてみましょう。

エラトステネスのふるいについてはウィキペディアの記事(これ)を参照して下さい。まず100万以下の整数を羅列して、2の倍数をすべて消す、3の倍数をすべて消す、4の倍数をすべて消す・・・という作業を1000まで繰り返します。最後までやると、素数のみが消えずに残るというしくみです。

こうして得られた素数のリストを、n の値を1ずつ増やしながら順にたどり、n が素数であれば和に加えます。n が素数かどうかの判定には、いま作ったふるいがそのまま利用できます。

結果は次の通りです。

結果、3475059124 という答が得られました。実際にはこのあと、問題ページにあるテキストボックスに回答を入力し、正解かどうかをチェックします。みごと合っていれば、正解アイコンが現れます。

初級編はわりと単純な問題でした。次の中級編では、ひと工夫が必要な、より難度の高い問題にトライしていきます。

トラックバック

このエントリーのトラックバックURL:
http://www.riverplus.net/cgi/mt/mt-tb.cgi/3034