ユークリッドの互除法

2 つの整数 a, b について最大公約数 (GCD) を求める。

1. 入力 a, b を絶対値へ変換する (負の数の考慮) 。
2. a, b のうち、大きい数値を m, 小さい数値を n (m ≧ n) とする。
3. n = 0 であるか評価する。
   • 真なら m を出力してアルゴリズムを終了する。この m が最大公約数となる。
   • 偽なら m を n で割った余りを新たに n とし、更に元の n を新たに m とし 3. に戻る。

参考文献

• ユークリッドの互除法 - Wikipedia
• ユークリッドの互除法をCanvasで可視化する