最大公約数と最小公倍数の求め方

2 つの正の整数について、最大公約数と最小公倍数を求めます。最大公約数は両方を割り切る数のうち最大のもの、最小公倍数は両方の倍数になっている数のうち最小のものです。

最大公約数はユークリッドの互除法で求めます。大きいほうを小さいほうで割り、割った数と余りの組に置きかえる。これを余りが 0 になるまで繰り返し、最後に残った数が最大公約数です。約数を全部書き出すより、ずっと速く求まります。

最小公倍数は、最大公約数さえ出ていれば次の式で求まります。

• $a$、$b$ — 1 以上の整数
• $\gcd(a, b)$ — 最大公約数
• $\mathrm{lcm}(a, b)$ — 最小公倍数

例

$a = 12$、$b = 18$ とします。互除法は次のように進みます。

• $18 \div 12 = 1$ 余り $6$
• $12 \div 6 = 2$ 余り $0$

余りが 0 になったので、最大公約数は 6 です。最小公倍数は

となり、36 です。

注意

• 入力は 1 以上の整数です。小数や 0 以下の値はエラーになります
• 手計算では、先に割ってから掛けると値が小さくて済みます。$\dfrac{12}{6} \times 18 = 36$ のようにすれば、216 を経由せずに求まります
• 2 数が互いに素（最大公約数が 1）のとき、最小公倍数は 2 数の積そのものです
• 一方が他方の倍数のときは、最大公約数が小さいほう、最小公倍数が大きいほうになります