問題 16

以下のように入力し、最大公約数、最小公倍数を求めよう。

ユークリッドの互除法

引き算を繰り返すことにより、最大公約数を求めることができます。例えば、18 と 12 の最大公約数を求めてみましょう。

18 > 12 ですから、18 - 12 = 6 となります。この減算の答えを r とおきます。12(小さい方）と6(rの値）の大きい方から小さい方を引きます。12 - 6 = 6 となります。6(小さい方）と6(r の値）に対して引き算をします。6 - 6 = 0 となりました。r = 0 となりました。この時の引いた数（引かれた数と同じ）が、最大公約数 (G.C.D.) です。

これを、アルゴリズムで表すと、以下のようになります。

1. 2つの整数値を入力
2. 大きい方を a、小さい方を b とする（同じ値の場合は、同じ値をaとbとする）。
3. r = a - b とする。
4. r ! = 0 の場合、
   1. r と b の大きい方を a、小さい方を r　とする。
   2. 3 へ飛び越し
5. r == 0 の場合、
6. b を 最大公約数とする。

プログラムは、以下のようになる。

最小公倍数（L.C.M.）は、以下の公式により求めることができます。２つの整数値をA、Bとします。

LCM = A*B／GCD

実は、r = a % b としても最大公約数を計算することができます。ユークリッドの互除法、つまり、除算を用いるためこの名前がつけられました。