Pythonで最大公約数（GCD・HCF）を求める方法をわかりやすく解説

最大公約数（GCD・HCF）とは？

最大公約数（Highest Common Factor：HCF、または Greatest Common Divisor：GCD）とは、2つ以上の整数に共通する約数の中で最も大きい正の整数のことです。余りが出ずに両方の数を割り切れる、最大の数を指します。

例えば、8と12の場合を考えてみましょう。

• 8の約数：1, 2, 4, 8
• 12の約数：1, 2, 3, 4, 6, 12

共通する約数は「1, 2, 4」なので、その中で最大の4が8と12の最大公約数となります。

for文を使ってGCDを求める基本的な方法

まずは、Pythonのfor文と条件分岐を使った基本的なアルゴリズムを見ていきましょう。この方法では、小さい方の数以下の範囲で、両方の数を割り切れる最大の整数を順番に探していきます。

x = int(input("1つ目の数値を入力してください: "))
y = int(input("2つ目の数値を入力してください: "))

if x > y:
    smaller = y
else:
    smaller = x

for i in range(1, smaller + 1):
    if ((x % i == 0) and (y % i == 0)):
        hcf = i

print(x, "と", y, "の最大公約数は", hcf, "です")

コードの解説

1. 入力の受け取り： input() 関数でユーザーから2つの整数を受け取り、int() で整数型に変換します。
2. 比較処理： if文で2つの数を比較し、小さい方の値を変数 smaller に代入します。最大公約数は必ず小さい方の数以下になるためです。
3. 繰り返し処理： for文で1から smaller までの数を順番に確認し、「x でも y でも割り切れる」数を見つけるたびに hcf 変数を更新します。ループが終わった時点で hcf には最大の共通約数が格納されています。

実行例

1つ目の数値を入力してください: 8
2つ目の数値を入力してください: 12
8 と 12 の最大公約数は 4 です

mathモジュールを使ったより簡単な方法

Pythonでは標準ライブラリの math モジュールに gcd() 関数が用意されているため、実は自前でアルゴリズムを実装しなくても1行で最大公約数を求められます。

import math

x = int(input("1つ目の数値を入力してください: "))
y = int(input("2つ目の数値を入力してください: "))

print(x, "と", y, "の最大公約数は", math.gcd(x, y), "です")

math.gcd() は内部で効率的なユークリッドの互除法を使用しているため、大きな数値を扱う場合でも高速に計算できます。学習目的でアルゴリズムを理解したい場合はfor文による実装、実務やパフォーマンスが重要な場面では math.gcd() の利用がおすすめです。

まとめ

• 最大公約数（GCD・HCF）は、複数の整数を余りなく割り切れる最大の正の整数である。
• for文と剰余演算子（%）を組み合わせることで、基本的なアルゴリズムを自分で実装できる。
• Pythonの math.gcd() 関数を使えば、ユークリッドの互除法による高速な計算を1行で実現できる。