エラトステネスの篩の素数判定プログラム(c#)

  • このエントリーをはてなブックマークに追加

スポンサーリンク

※サイト運営にサーバーは必須です※
~このサイトもエックスサーバーを使用しています~

はじめに

素数のリストを可能な限り早く作ってくれるプログラムを作りたいと思って、最初はいくつか作って実行スピードを調べようと思った。

だが、いくつか作った結果、実行するタイミングで結構結果が変わる。
自分でもどのパターンが最速かよくわかっていない。

オーダーで2倍も違うものはないので、どれを使ってもいいと思う。

※言語はC#。作った環境はVisual Studio 2015 。コンソールアプリケーションで作っている

※追記:バグが残っている可能性がある。

1:単純なエラトステネスのふるい

 

何も考えず、愚直にエラトステネスのふるいを実装した場合。
配列をラベル付けする数字が0から始まるのに対して、配列の中の数字は1から始まっていると考えている。その食い違いに解消のためにi+1になっている所がある。

※わかりづらいかもしれないが、素数をFalse、素数以外の数字をTrueと判定している(配列の中が最初はFalseなので)。

2:√Nで、篩を止める

素数リストを作るときに、考えている最大の数をNとするとその平方根までの数で篩をかければ十分である。ループ文で毎回(i+1)*(i+1)で判定しているのが遅さの原因のような気がしてきたので、次のコードでは、そこも含めて改善

3:奇数の場合で考える(読み取りのみ)

篩の中のループ文の条件判定に、Sqrt()を使っている。これで少しは早くなるはず。

また、2だけ特別扱いにして結果をコンソールに出力する時に2つ飛ばしで行っている。

あと、(i + 1) * j – 1を無駄に2回計算しているのが気になってきた(forの判定とn_list[]で)。だが、色々いじくっても、逆に遅くなったので、手を加えていない。

4:奇数の場合で考える(篩+読み取り)

篩の部分でも2だけ特別扱いにしている。ぶっちゃけそんなに早くなっている感じはしなかった。

4´:奇数の場合で考える(篩+読み取り)

後でよくよく考えたら、篩の中のforのループ文(int j)の部分も2つ飛ばしで問題ない気がしてきた。ついでに、jのスタートは自分自身の数からスタートしても大丈夫だ思う。

例えば、7を素数として見つけた場合。篩をかけるのを14からスタートするのではなく、49から始めても問題ない。なぜなら、14、21、28、35、42は全て2,3,5のいずれかの倍数なので、すでに素数でないとわかっている。

また、49(7×7)の次として56(7×8)を考えるのでなく、63(7×9)を考えればいい。56は2の倍数なので素数でないとわかっている。つまり、2つ飛ばしで考え7×(奇数)を消していく。

 

 

5:6k+(1,5)で考える(読み取り)

 

読み取り時に、2と3を特別扱いする。
この場合、6k+{1,5}を考えれば十分。

プログラム的には、数字が+2されるのと+4されるのが交互に続く。

交互に+2と+4をするための判定にif~else文を使っている分、むしろ遅くなった気がする。6k+{1、-1}と考えても似たような問題に直面するはず。

 

まとめ

何度か実行した体感としては、3か4が1と比べて速くなった気がする。そんなに大きな差はないが

関連記事

この記事の経験を踏まえ、より大きな素数に対応したプログラムの紹介

無料体験レッスンあり。マンツーマン形式で初心者向け。
  • このエントリーをはてなブックマークに追加

スポンサーリンク

コメントを残す

*

日本語が含まれない投稿は無視されますのでご注意ください。(スパム対策)