読者です 読者をやめる 読者になる 読者になる

【アルゴリズムの勉強】Rubyでユークリッドの互除法を書いてみる

ユークリッドの互除法によって2つの自然数の最大公約数を求める処理をRuby再帰を用いて実装する。

ユークリッドの互除法とは

ユークリッドの互除法ユークリッドのごじょほう、英: Euclidean Algorithm)は、2 つの自然数の最大公約数を求める手法の一つである。
2 つの自然数 a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。
明示的に記述された最古のアルゴリズムとしても知られ、紀元前300年頃に記されたユークリッドの『原論』第 7 巻、命題 1 から 3 がそれである[注釈 1]。

ユークリッドの互除法 - Wikipedia

Rubyで実装

def euclid_gcd(x, y)
  return x if y == 0
  euclid_gcd(y, x % y)
end

p euclid_gcd(8, 20)
# => 4
p euclid_gcd(100, 200)
# => 100
p euclid_gcd(1, 12)
# => 1

参考文献、参考リンク