ユークリッドの互除法
2 つの整数 a, b について最大公約数 (GCD) を求める。
- 入力 a, b を絶対値へ変換する (負の数の考慮) 。
- a, b のうち、大きい数値を m, 小さい数値を n (m ≧ n) とする。
- n = 0 であるか評価する。
- 真なら m を出力してアルゴリズムを終了する。この m が最大公約数となる。
- 偽なら m を n で割った余りを新たに n とし、更に元の n を新たに m とし 3. に戻る。
参考文献
v0.3.0on 2025-02-26
2 つの整数 a, b について最大公約数 (GCD) を求める。