フリーランス チャレンジ!!

フリーランス チャレンジ!!

現役フリーランスエンジニアが書く雑記ブログ

【Go言語】エラトステネスの篩(ふるい)で素数を求めるプログラム(10万まで調べても0.02秒)

スポンサーリンク

スポンサーリンク

エラトステネスの篩 ふるい 素数

素数を求めるのに単純に判定するより、エラトステネスの篩を使えば計算量が少なくなるため処理が高速になります。

 

アルゴリズムとかあまり知らずにプログラム組んでる人はぜひ呼んでください。

ちょっと世界が変わりますよ!

(アルゴリズム勉強しようって気になります)

 

エラトステネスの篩

エラトステネスの篩 (エラトステネスのふるい、英: Sieve of Eratosthenes) は、指定された整数以下の全ての素数を発見するための単純なアルゴリズムである。古代ギリシアの科学者、エラトステネスが考案したとされるため、この名がある。

引用:wikipediaより

 


尚、エラトステネスの篩のアルゴリズムは以下の通りです。

1:2 から n までの整数を並べる。
2:生き残っている数の中で一番小さい(かつまだ p として使われていない)ものを新たに p とおき,p 以外の p の倍数を全て消していく。
3:2の操作を繰り返していき,p が n−−√ を越えたら終了。最終的に生き残ったものが素数。

 引用:エラトステネスのふるいとその計算量 | 高校数学の美しい物語

 

最近マイブームのGo言語でプログラムします。

 

エラトステネスの篩を使わないロジックとどのくらい処理時間に差があるかも確認してみます。

 

 

なぜエラトステネスの篩が速いのか?

そもそもなぜエラトステネスの篩が速いのでしょうか?

 

アルゴリズムを見てもピンとこないので、実例をあげて確認しましょう。

 

実例として0〜100までの数で素数を求めます。

※実際、0と1は素数では無いのでプログラムは2〜100の数から素数を求めます。

 

ちなみに素数とは1と自分自身以外で割り切れない数のこと。(3、5、7とか・・・)

 

通常の素数を求めるプログラム

2から100まで1つずつ自分以外で割れるかチェックしていきます。

 

①まず"2"を調べる

②"2"は"3"で割れるか? 割れない次の数を調べる

③"2"は"4"で割れるか? 割れない次の数を調べる・・・

④これを"100"まで調べて、割れないことがわかったので素数

 

このように素数の場合は、100までチェックしなければいけません。

ただ、素数でない例えば"4"の場合は、最初の"2"で割り切れるのですぐチェックが終わります。

 

エラトステネスの篩のプログラム

次にエラトステネスの篩ですが最大数の平方根までチェックすればOKです。

 

100の平方根は10なので2〜10までチェックすればいい。

そしてリストから調べてる数の倍数をふるい落とします。

 

実例でみてみましょう。

 

①まず"2"を調べる

②"2"で割れる数をリストから削除(4,6,8,10,12,14・・・)

③"3"で割れる数をリストから削除(15,21,27,33・・・)

④これを"10"まで調べて、リストに残った数が素数

 

エラトステネスの篩が速い理由

 ここまで通常のプログラムとエラトステネスの篩のプログラムの違いが分かったと思います。

 

なぜエラトステネスの篩が速いのか?

 

それはチェックする数です。

 

通常のプログラムは2〜100まで88回チェックしなければいけませんが、エラトステネスの篩は2〜10まで8回チェックすればOKです。

 

計算量が全然違うのでエラトステネスの篩が速いというわけです。

 

次にプログラムをみてみます。

 

エラトステネスの篩のプログラム

ポイントは5行目で平方根を求め、11行目のforループは平方根の値までしかループしません。 

gist3ed2096a8508c50067cedb3bab9042d4

 

普通のプログラム

gista8cd5ec2418d7d89fd3764b6efe39bff 

 

処理時間を計測

 さて、本当にエラトステネスの篩が速いのかプログラムを動かし処理時間を計測しました。

 

プログラムは下記です。(Go言語)

gist05a83ff5a238e13a3cc3717a82206e4e

 

実行結果はこんな感じ

f:id:ksakae1216:20180712105424p:plain

 

素数を求める数は2〜10万まで。

3回実行して平均は下記の通りでした。

エラトステネスの篩:0.02秒

普通に素数を求める:4.34秒

 

全然違いますね。

 

最後に

 処理数が多い場合、このような効果的なアルゴリズムを知っていて実装すればかなり処理時間が短縮されます。

 

数学(アルゴリズム)の勉強も必要だなと痛感しました。

 

最初はこの辺からかな〜〜