自然な言語を目指して

技術・日常をぐだぐだと

ユークリッドの互除法

最近競プロをしていますが、アルゴリズムと数学が本当に弱すぎることを実感する日々です。

基本中の基本、最大公約数・最小公倍数を求めるアルゴリズムユークリッドの互除法について備忘録を書こうと思います。 Rubyにて実装しました。

input_value_array = gets.split.map(&:to_i)
input_value_array.sort!


loop{
  remainder = input_value_array[1] % input_value_array[0]
  break if remainder == 0
  input_value_array[1] = input_value_array[0]
  input_value_array[0] = remainder
}

puts input_value_array[0]