ユークリッドの互除法
ふたつの
自然数
m
と
n
（ただし
m ≤ n
）の
最大公約数
を求めるための方法
m = n
の場合、
m
が最大公約数
m != n
の場合、
m
と
n
の最大公約数は
n - m
と
m
の最大公約数に等しいという性質を利用する
最大公約数の定義が
再帰
的
最も古い記述が紀元前300年代に書かれた
ユークリッド
の著作にあることからこの名前がついた
https://algo-logic.info/euclidean-algolithm/
Rubyでは
Integer#gcd
,
Integer#lcm
,
Integer#gcdlcm
がビルトインで用意されている
https://docs.ruby-lang.org/ja/latest/method/Integer/i/gcd.html
https://docs.ruby-lang.org/ja/latest/method/Integer/i/lcm.html
https://docs.ruby-lang.org/ja/latest/method/Integer/i/gcdlcm.html