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

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

ソースコード

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"

実行

$ 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

解説

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

リンク

色々なプログラム言語でアルゴリズム学習

• Javascript
• PHP
• Python
• Shell
• AWK
• C言語
• Go言語
• Ruby