ユークリッドの互除法を 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
なお、最大公約数・最小公倍数を求めるメソッドは、組み込みライブラリに既に存在しています。念のため。ただ、三つ以上の数を扱っているかどうかは知りません。
ぐぐってみると、ユークリッドの互除法を使っておらず、力任せに最大公約数を求めている人が結構多いですね。