最大公約数、最小公倍数の求め方/ユーグリットの互除法

今回もアルゴリズムに関して学んだ知識のメモ。ユーグリットの互除法について調べてみました。

ユーグリットの互除法とは

最大公約数を求める手法です。

ユークリッドの互除法（ユークリッドのごじょほう、英: Euclidean Algorithm）は、2 つの自然数の最大公約数を求める手法の一つである。

https://ja.wikipedia.org/wiki/%E3%83%A6%E3%83%BC%E3%82%AF%E3%83%AA%E3%83%83%E3%83%89%E3%81%AE%E4%BA%92%E9%99%A4%E6%B3%95

高校数学なんかでも学ぶ内容ですし、かなり有名なアルゴリズムですね。

ユーグリットの互除法のアルゴリズム

割り算で求めるやり方と引き算で求めるやり方があります。
以下、それぞれのやり方での整数aとb(a >= b)の最大公約数の求め方を記載します。

割り算バージョン

1. aをbで割った余りを求める。
2. 余りが0の場合、bが最大公約数。
3. 余りが0以外の場合、除数(割った数)を先程の余りで割りその余りを求める。
4. これを余りが0になるまで繰り返す。余りが0になった時の除数が最大公約数

引き算バージョン

1. aをbで引いた差を求める。
2. 差が0の場合、bが最大公約数。
3. 差が0以外の場合、引いた数と差の大きい方から小さい方を引いた差を求める。
4. これを差が0になるまで繰り返す。差が0になった時の減数(引いた数)が最大公約数

計算量としては割り算で求めるやり方のほうが少ないかと思われます。

最小公倍数の求め方

最大公約数が求めることができれば、最小公倍数は以下の式で求める事が出来ます。

A,Bの最小公倍数＝A×B÷A,Bの最大公約数

実装

というわけで、今回もRubyで実装してみます。

#割り算バージョン
def gcd(a, b)
  a, b = b, a if a < b
  loop do
    m = a % b
    return b if m == 0
    a, b = b, m
  end
end

#引き算バージョン
def gcd2(a, b)
  loop do
    a, b = b, a if a < b
    d = a - b
    return b if d == 0
    a, b = b, d
  end
end

#最小公倍数
def lcm(a, b)
  return ((a * b) / gcd(a, b))
end

puts gcd(1071, 1029)#=>21
puts gcd2(1071, 1029)#=>21
puts lcm(1071, 1029)#=>52479

おまけ

ま、Rubyの場合は標準でメソッドが用意されているんですけどねー。

puts 1071.gcd(1029)#=>21
puts 1071.lcm(1029)#=>52479

解法の中身を理解する事も重要だと思います。