とがみんブログ
大学院の中退を決断し、徹底的に自分と向き合い就職活動をする中で、心理学や脳科学に興味を持つ。挙げ句の果てに、この世界の仕組みにも興味を持つ。そんなとがみんの考えや経験を綴ったブログです。
アルゴリズム

【アルゴリズム】素数を高速で表示するプログラム(エラトステネスのふるい)

どうも。とがみんです。

この記事では素数を表示するプログラムを考えていきます。

一番思いつきそうなやり方と、「エラトステネスのふるい」というアルゴリズムを紹介し、それらのプログラムの動作速度を比較します。

プログラムはPHP言語で書いています。

素数とは

「素数」とは1と自分自身以外の正の約数を持たない自然数のことです。

自然数は「1,2,3,4…」と1から始め、1を順に足して得られる範囲の数です。

正の約数とは、1以上で、ある数Nを割り切ることのできる整数です。

つまり、素数とは、

「1,2,3,4…」と1を順に足して得られる範囲の数の中で、1と自分自身以外に割り切ることができる正の整数がない数のこと

です。

「2」は1と2以外の正の整数で割り切れないので素数

「3」は1と3以外の正の整数で割り切れないので素数

「4」は1と4以外に、2で割り切れるので素数ではない

「5」は1と5以外の正の整数で割り切れないので素数

「6」は1と6以外に、2と3で割り切れるので素数ではない

・・・

といった感じです。

100までの素数だけを並べるとこんな感じです。

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

それら全ては「1とその数自身」以外では割り切ることができません。

スポンサードリンク

素数を表示するプログラム

すぐに思いつくアルゴリズム

おそらく、誰もが一番最初に思いつく方法について紹介します。

素数は「1とその数自身」以外で割り切ることができない数なので、ある数が素数であるか素数でないかを判定するためには、

その数を「2からその数より1低い数」まで割り、割り切れたら素数でない。割り切れなかったら素数である。

と言う風に判定します。実際のコードが以下です。

処理速度が速いアルゴリズム

素数を表示するにあたって、「エラトステネスのふるい」といった古代ギリシアの科学者であるエラトステネスが考案したとされる、素数を発見するためのアルゴリズムがあります。

手順は以下の通りです。

  1. 2から100までの整数を並べる(1は素数じゃないので省く)
  2. 並べた(残った)整数の最初のもの(次の数)が素数(pとする)
  3. pの倍数は素数ではないので、除去する(pの2乗から考え始める)
  4. pの2乗が100を超えるまで②と③を繰り返す
  5. 残った数が全て素数

50までの例を下の写真で説明します。

①まず、2から50までの整数を並べます。

②並べた数の最初の数が素数です。「2」が素数にあたります。

③次に素数「2」の倍数を除去します。

④残った数の中で、「2」の次の数は「3」です。この「3」が素数であり、「3」の倍数で除去します。

これを「7×7 < 50 <11×11(7 < √50 < 11)」なので、「7」まで続ける。

「7」の倍数を除去した時点で、「2〜7」までの倍数は全て除去されています。

次に消去すべき対象は「11×11」。ただこの数は50より大きいので、判定する数に含まれていない。

なので、これ以降は考える必要がない。

⑤残った数が素数になります。50までの素数は「2,3,5,7,11,13,17,19,23,29,31,37,41,43,47」です。

これをコードで書くと以下のようになります。

処理速度の比較

上記のコードの処理速度を比較します。

処理の速度を測る場合は以下のコードを利用します。

上記で説明してきた、プログラムの処理速度を比較します。

時間(秒)、横軸はいくつまでの素数を表示するか。

青い線は初めに紹介したプログラム①。

赤い線はエラトステネスのふるい。

表示する素数の数が大きくなればなるほど、プログラム①の処理速度は指数関数的に増加していきます。

「エラトステネスのふるい」の方は、表示する素数の数が大きくなっても計算量が①ほど増加しないので、処理速度が非常に速いです。

まとめ

素数の表示に関するアルゴリズムとプログラムの書き方を紹介しました。

プログラムを書く際は処理速度も意識したいところですね(笑)

スポンサードリンク