[アルゴリズム] 1から100までの素数を取得(Ruby編）
素数の算出って内容自体はシンプルなのだが、素数を求める時に問題になるのは、対象の数が素数かどうかの判定をする際に
対象の数よりも少ない数字で全て割ってみて、割り切れる数が存在するかどうかという事を確認しなければならない。
とすると、１０までの数をチェックする場合、
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
３３０回のif文が繰り返されているわけだ。
桁が上がっていくと恐ろしい数になることが容易に想像できるのだが、もっと簡単にチェックする方法があるのだろうか？
ホントはそういう事を追求することがアルゴリズムの真髄なのだと思う。
そんなことを考えつつ、C言語言語の変換コードに徹するだけなのだが・・・
ソースコード
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
def getPrimeNumber(num) flg = 0 (2).step(num-1 , 1){ |i| if num % i == 0 then flg = i break end } return flg end numbers = [] (2).step(100,1){ |i| if getPrimeNumber(i) == 0 then numbers.push(i) end } print numbers,"\n" |
実行
|
1 2 3 4 5 6 |
$ time ruby prime_number.rb [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] real 0m0.060s user 0m0.041s sys 0m0.010s |
解説
今回のソースコードは何も新規性がありません。
ということで、処理速度計測をしておきます。
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