RubyでEuclidの互除法

Euclidの互除法をRubyでかいてみた。
2つの自然数の入力に対して、それらの最大公約数を求める、というもっとも有名なアルゴリズムである。

まずはソース

a = gets.chomp.to_i
b = gets.chomp.to_i

if b > a
  a,b = b,a
end

while true
  if (a%b) == 0
    puts b
    break
  else
    a,b = b,(a%b)
  end
end

流れは

  • 入力はa,bを得る
  • a>bとなるように値を入れ替える。

− a/bの剰余が0(aがbで割り切れる)ときbが最大公約数なので、bを出力してループを抜ける

  • a/bの剰余が0でない(aがbで割り切れない)とき、aにbを、bにa%bを格納し、再度剰余を求める処理へ

もう少し単純に書けそうな気も