[アルゴリズム] 1から100までの素数を取得(Ruby編)

mathematics-80449_1280
LINEで送る
Share on GREE
Share on LinkedIn

素数の算出って内容自体はシンプルなのだが、素数を求める時に問題になるのは、対象の数が素数かどうかの判定をする際に
対象の数よりも少ない数字で全て割ってみて、割り切れる数が存在するかどうかという事を確認しなければならない。
とすると、10までの数をチェックする場合、
2×1,3×2,4×3,5×4,6×5,7×6,8×7,9×8,10×9
という数分の余剰を確認しなくてはいけない。
これら全て足すと
2+6+12+20+30+42+56+72+90 = 330
330回のif文が繰り返されているわけだ。
桁が上がっていくと恐ろしい数になることが容易に想像できるのだが、もっと簡単にチェックする方法があるのだろうか?
ホントはそういう事を追求することがアルゴリズムの真髄なのだと思う。
そんなことを考えつつ、C言語言語の変換コードに徹するだけなのだが・・・

ソースコード

実行

解説

今回のソースコードは何も新規性がありません。
ということで、処理速度計測をしておきます。

1〜100

0.060s

1〜1000

0.074s

1〜10000

0.416s

1〜100000

24.214s

1〜1000000

34m22.661s

リンク

素数計算プログラム

Javascript
PHP
Python
Shell
AWK
Go言語
Ruby

アルゴリズム過去記事

http://wordpress.ideacompo.com/?cat=562&tag=Algorithm

Leave a Reply

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です