Ruby:覚書（最大公約数を求めるメソッド）

Rubyを勉強しているので、最大公約数を求めるメソッドを作成したいと思います。
まずは約数を求めるメソッドを考えました。
単に余りが０となった値を取得してもいいのですが、計算回数をなるべく少なくしたいと思い、自分なりにアルゴリズムを考えました。（年なので頭を使うと疲れる・・・でもちょっとたのしいですね。自分で考えるというのは。）

整数の場合、必ず２で割り切れます。奇数の場合は２で割りきれませんが、２で割った商より大きい約数はないわけですね・・・。
ということで、

• 対象は自然数なので、１は必ず約数となります。
• 約数は２から確認を始めればOK

以下のメソッドdivisor_allを考案しました。 引数valが約数を求める対象です。

def divisor_all val
  result = [1] #1は必ず約数
  divisor = 2 #2で割って商を求める
  quotient = val/divisor
  while divisor < quotient #割る数と商を比較し商が割る数を下回った時点で終了
    if val % divisor == 0
      quotient = val/divisor
      result << divisor
      result << quotient
      p [result, divisor] #計算状況をとりあえずプリント
    end
    divisor += 1
  end
  result
end

こんな感じでいかがでしょうか。約数のみループさせるのではなく、余りが0のときは、商の方も約数になりますのでそれを取得しているのがポイントですね。

続いてこの約数を求めるメソッドを利用し、最大公約数を求めるメソッドです。

#最大公約数を求める
def common_divisor_max arr
  arr2 = []
  arr.each_with_index{|val, i| arr2 << (divisor_all arr[i])}
  p arr2 # 約数を確認するためプリント
  common_div = arr2.inject{|a1, a2| a1 & a2}
  common_div_max = common_div.sort.pop
end

ここで

p common_divisor_max [9, 12, 15]

を試せば、3が求められると思います。 Array#inject って一体どこで使うのだろうと思っていたけれど、こんなところで意外と使える・・・inject 

ユークリッドの互除法（２つの値の場合）

その後、ネットで調べてみると、ユークリッドの互除法というのがあるそうで・・・。

def gcd(n, m)

  n, m = m, n if m > n
  #p [n, m]

   loop {
    r = n % m
    break if r == 0
    n, m = m, r
  }
  m
end

2つの数値の最大公約数は上記のような処理で求められるらしい。

複数の（３つ以上の）自然数の最大公約数を求める

 配列に複数の自然数があった場合、やはりArray#injectが使えるようです。

arr = [30,120,15,60]
p arr.inject{|a, b| gcd(a, b)}

たったこれだけで済んでしまいます。

また、先に考えたものはいったんすべての公約数を求めているので、
その解を利用するなら使えそうです。

久々に勉強になりました。