最大公約数とユークリッドの互除法

最大公約数（GCD）は、2つ以上の整数に共通する約数のうち最大のものです。ユークリッドの互除法は、大きい方の数を「大きい方を小さい方で割った余り」に置き換えることを繰り返して、最大公約数を効率よく求めるアルゴリズムです。

■ 試験で押さえるポイント

• aをbで割った余りをrとすると、aとbの最大公約数は、bとrの最大公約数に等しくなります。余りが0になったときの割る数が最大公約数です。

• 割り算の代わりに引き算を使う方法もあります。大きい方から小さい方を引いても最大公約数は変わらないので、2つの値が等しくなるまで「大きい方 ← 大きい方 − 小さい方」を繰り返し、等しくなった値が最大公約数です。

• 繰返しの回数は事前に分からないので、forではなく while (x ≠ y) のように条件で繰り返します。

• 最小公倍数は、a × b ÷ 最大公約数 で求められます。

x ← num1
y ← num2
while (x ≠ y)
  if (x ＞ y)
    x ← x − y
  else
    y ← y − x
  endif
endwhile
return x

割り算の互除法なら、24 ÷ 18 ＝ 1 余り 6、18 ÷ 6 ＝ 3 余り 0 なので、最大公約数は6です。

■ 選択肢での判断ポイント

1回だけ判定するifではなく、xとyが等しくなるまで繰り返すwhileが必要です。また、x ＞ y のときに x ← x − y とする（大きい方から小さい方を引く）組合せになっているかを確認します。