# Ruby入門＞ Ruby tips

素数を調べるアルゴリズムを検証しメソッド定義

ある整数が素数かどうかを調べるメソッドを考えてみます。
素数とは、その整数自身と1以外の整数で割り切ることができない数のことです。
1桁の素数は、「2, 3, 5, 7」となります。（1は素数に含めない。）

素数を求めるアルゴリズムを考えてみてすぐに思いつく方法は、その整数（n）までの数字すべて（2からn-1まで）で割ってみて、割り切れるかどうか調べる、という方法です。
このアルゴリズムでメソッド定義して実行してみます。

def prime_first?(num)
  # numまでの数字で、numが割り切れるか調べる
  2.upto(num-1){|i|
    if num % i == 0
      return false  # 割り切れたら素数でない
    end
  }
  return true
end
 
puts prime_first?(17)
puts prime_first?(36)
 
# 100までの整数のうち素数をリストアップ
2.upto(100){|i|
  if prime_first?(i)
    print i, ", "
  end
}

実行結果。

true
false
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,

ある整数が素数かどうかを調べたり、１から100までの素数のリストアップがしっかりと実行されます。
しかしながら・・・
実は、このアルゴリズムには、無駄な計算が多く含まれています。

たとえば、36が素数かどうかを調べる場合・・・
36の約数は、「2, 3, 4, 6, 9, 12, 18」となります。（1と36を除く約数）
そして、36は・・・

36 = 2 x 18
36 = 3 x 12
36 = 4 x 9
36 = 6 x 6
36 = 9 x 4
36 = 12 x 3
36 = 18 x 2

と表すことができます。
ここで注目するのは、「2 x 18」と「18 x 2」、「3 x 12」と「12 x 3」、「4 x 9」と「9 x 4」はオペランドをひっくり返しただけで、同じ計算を行っているということ。

すなわち、36が素数かどうかを調べるためには、36の平方根である6までの範囲（36 = 6 x 6）の数で、36が割り切れるかどうかを調べれば良いということになります。
ある整数が素数かどうかを判別するためには、その整数の平方根までの整数で割り切れるかどうかを調べる、というアルゴリズムが成り立ちます。
こうすると、計算回数を大幅に減らすことができます。以下、そのメソッド定義です。

def prime?(num)
  # numの平方根までの数字で、numが割り切れるか調べる
  sqrt_num = Math.sqrt(num).floor
  2.upto(sqrt_num){|i|
    if num % i == 0
      return false  # 割り切れたら素数でない
    end
  }
  return true
end
 
puts prime?(17)
puts prime?(36)
 
# 100までの整数のうち素数をリストアップ
2.upto(100){|i|
  if prime?(i)
    print i, ", "
  end
}

実行結果。

true
false
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,

最初のメソッドと同じ実行結果です。

>> 次の記事 : WWW::Mechanizeをインストール

<< 前の記事 : ディレクトリに含まれるファイルの、ソースコード行数の総数を返すメソッド