ユークリッドの互除法を Ruby で

ユークリッドの互除法(Euclidean Algorithm)を使って、最大公約数を求めます。99400891 と 99221377 の最大公約数は 9973 です。プログラムは以下のとおり。再帰を使う典型的な問題でしょう。

def ea(m, n)
  return m if n == 0
  ea(n, m % n)
end

puts ea(99400891, 99221377)   #=>9973

これを使えば、最小公倍数も簡単に求められます。

def lcml(m, n)
  m * n / ea(m, n)
end

puts lcml(48, 28)   #=>336


三つ以上の数の最大公約数、最小公倍数を求めるには、配列を使ってこんな感じでしょうか。

class Array
  def gcd
    inject {|a, b| ea(a, b)}
  end

  def lcm
    inject {|a, b| lcml(a, b)}
  end
end

puts [60, 48, 36].gcd    #=>12
puts [14, 10, 24].lcm    #=>840

 
なお、最大公約数・最小公倍数を求めるメソッドは、組み込みライブラリに既に存在しています。念のため。ただ、三つ以上の数を扱っているかどうかは知りません。

ぐぐってみると、ユークリッドの互除法を使っておらず、力任せに最大公約数を求めている人が結構多いですね。