整数の最大公約数（GCD）を求めるとき、まずは基本的な考え方を押さえることが大切です。愚直にやる方法と、効率的なユークリッド互除法があります。
最大公約数とは？
2つ以上の整数に共通する約数のうち、最も大きい整数を最大公約数と呼びます。例えば、12と18の最大公約数は6です。
愚直法での求め方
愚直に求める場合は、小さい方の数から1ずつ減らして、両方を割り切れる数を探します。例：12と18の場合、12から順に割り切れる数を探すと、6が最大公約数になります。
ただし、数が大きくなると手作業では非常に煩雑です。
ユークリッド互除法
ユークリッド互除法は最大公約数を効率的に求める方法です。手順は次の通りです。
- 大きい方の数を小さい方の数で割る。
- 余りを次の小さい方として、再び前の小さい方で割る。
- 余りが0になったとき、割った数が最大公約数。
例：18と12の場合、18 ÷ 12 = 1 余り 6 → 12 ÷ 6 = 2 余り 0 → GCDは6
まとめ
・最大公約数は整数の共通約数の中で最大の数
・愚直法は理解に有効だが大きい数には不向き
・ユークリッド互除法は効率的で手作業でも計算が簡単
・まずは愚直法で考え方を理解し、慣れたら互除法を使うと良い
コメント