素数を求めるのに単純に判定するより、エラトステネスの篩を使えば計算量が少なくなるため処理が高速になります。
アルゴリズムとかあまり知らずにプログラム組んでる人はぜひ読んでください。
ちょっと世界が変わりますよ！
（アルゴリズム勉強しようって気になります）
エラトステネスの篩
エラトステネスの篩 (エラトステネスのふるい、英: Sieve of Eratosthenes) は、指定された整数以下の全ての素数を発見するための単純なアルゴリズムである。古代ギリシアの科学者、エラトステネスが考案したとされるため、この名がある。
引用：wikipediaより
尚、エラトステネスの篩のアルゴリズムは以下の通りです。
1：2 から n までの整数を並べる。
2：生き残っている数の中で一番小さい（かつまだ p として使われていない）ものを新たに p とおき，p 以外の p の倍数を全て消していく。
3：2の操作を繰り返していき，p が n−−√ を越えたら終了。最終的に生き残ったものが素数。
最近マイブームのGo言語でプログラムします。
エラトステネスの篩を使わないロジックとどのくらい処理時間に差があるかも確認してみます。
なぜエラトステネスの篩が速いのか？
そもそもなぜエラトステネスの篩が速いのでしょうか？
アルゴリズムを見てもピンとこないので、実例をあげて確認しましょう。
実例として０〜１００までの数で素数を求めます。
※実際、０と１は素数では無いのでプログラムは２〜１００の数から素数を求めます。
ちなみに素数とは１と自分自身以外で割り切れない数のこと。（３、５、７とか・・・）
通常の素数を求めるプログラム
２から１００まで1つずつ自分以外で割れるかチェックしていきます。
①まず”２”を調べる
②”2″は”3″で割れるか？ 割れない次の数を調べる
③”2″は”4″で割れるか？ 割れない次の数を調べる・・・
④これを”100″まで調べて、割れないことがわかったので素数
このように素数の場合は、１００までチェックしなければいけません。
ただ、素数でない例えば”4″の場合は、最初の”2″で割り切れるのですぐチェックが終わります。
エラトステネスの篩のプログラム
次にエラトステネスの篩ですが最大数の平方根までチェックすればOKです。
１００の平方根は１０なので２〜１０までチェックすればいい。
そしてリストから調べてる数の倍数をふるい落とします。
実例でみてみましょう。
①まず”２”を調べる
②”2″で割れる数をリストから削除（4,6,8,10,12,14・・・）
③”3″で割れる数をリストから削除（15,21,27,33・・・）
④これを”10″まで調べて、リストに残った数が素数
エラトステネスの篩が速い理由
ここまで通常のプログラムとエラトステネスの篩のプログラムの違いが分かったと思います。
なぜエラトステネスの篩が速いのか？
それはチェックする数です。
通常のプログラムは２〜１００まで８８回チェックしなければいけませんが、エラトステネスの篩は２〜１０まで８回チェックすればOKです。
計算量が全然違うのでエラトステネスの篩が速いというわけです。
次にプログラムをみてみます。
エラトステネスの篩のプログラム
ポイントは５行目で平方根を求め、１１行目のforループは平方根の値までしかループしません。
gist3ed2096a8508c50067cedb3bab9042d4
普通のプログラム
gista8cd5ec2418d7d89fd3764b6efe39bff
処理時間を計測
さて、本当にエラトステネスの篩が速いのかプログラムを動かし処理時間を計測しました。
プログラムは下記です。（Go言語）
gist05a83ff5a238e13a3cc3717a82206e4e
実行結果はこんな感じ
素数を求める数は２〜１０万まで。
３回実行して平均は下記の通りでした。
エラトステネスの篩：0.02秒
普通に素数を求める：4.34秒
全然違いますね。
最後に
処理数が多い場合、このような効果的なアルゴリズムを知っていて実装すればかなり処理時間が短縮されます。
数学（アルゴリズム）の勉強も必要だなと痛感しました。
最初はこの辺からかな〜〜
コメント