最大公約数と最小公倍数

[ うえ ]

問題 16

2つの整数値を読み込み最大公約数最小公倍数を求めよ。ユークリッドの互除法を用いよ。

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


ユークリッドの互除法

引き算を繰り返すことにより、最大公約数を求めることができます。例えば、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 とする(同じ値の場合は、同じ値をabとする)。
  3. r = a - b とする。
  4. r ! = 0 の場合、
    1. r と b の大きい方を a、小さい方を r とする。
    2. 3 へ飛び越し
  5. r == 0 の場合、
  6. b を 最大公約数とする。

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

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

LCM = A*B/GCD


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


[ うえ ]
yasu@i.hosei.ac.jp