Pythonアルゴリズム

Pythonでユークリッドの互除法を使って最大公約数を求める

このレッスンでは、ユークリッドの互除法で2つの数の最大公約数(GCD)を求めます。

  • 中級
  • 約2分で読めます
  • 実行できるサンプル 1 件

はじめに

どんな問題を解決するか

分数を約分するとき、ものを同じ大きさのグループに分けるとき、そして多くのパズルで、2つの数の両方を割り切る最大の数が必要になります。候補を1つずつすべて試す方法は、数が大きいと時間がかかります。ユークリッドは2,000年以上前に、ずっと速い方法を見つけました。

身近なたとえ

ユークリッドの方法は、長方形をできるだけ大きな正方形のタイルで敷き詰めるようなものです。48 × 18 の長方形から、切り取れるいちばん大きな正方形を切り取り、残った部分からも同じように切り取っていきます。余りが出ずにぴったり切り分けられたら、最後の正方形の一辺が答えです。

正方形の切り取りからコードへ
first, second▭ 長方形:48 × 18
first % second✂️ 短い辺を一辺とする正方形を切り取った残り
first, second = second, first % second🔁 残った部分で同じことを繰り返す
while second:✅ 余りなし:その一辺が最大公約数の6
余りが0になるまで gcd(a, b) = gcd(b, a % b) を繰り返します。
ひと言でいうと

2つの整数の最大公約数(GCD)は、その両方を割り切る最大の正の整数です。ユークリッドの互除法では、b が0になるまで、組 (a, b) を (b, a % b) に置き換えることを繰り返して求めます。

重要なポイント

  1. first, second = second, first % second で、2つの数の組を、小さいほうの数と余りの組に置き換えます。
  2. 48と18では、組は (48, 18)、(18, 12)、(12, 6)、(6, 0) と変わります。
  3. while second: は余りが0になると止まります。
  4. return abs(first) は負の入力でも正の結果を返します。

どんな場面で使う?

  • 分数や比を約分する。
  • 最小公倍数を求める:a * b // gcd(a, b)。
  • 数のパズル、剰余演算(余りを使う計算)、暗号の基礎。

使わなくてよいとき

  • 実際のコード:標準で math.gcd が用意されていて、最近の Python では引数をいくつでも渡せます。
  • すべての公約数を求める場合:最大公約数で分かるのは、いちばん大きい公約数だけです。

サンプルコード

コードを実行 →
main.py
def gcd(first, second):
    while second:
        first, second = second, first % second
    return abs(first)

print(gcd(48, 18))
この例の実行ボタンを作成

実行結果

6

コードの解説

各ステップで、ペア(first, second)を(second, first % second)に置き換えます。余りが0になったとき、firstに残った値が最大公約数なので、48と18の最大公約数は6です。abs()関数で結果が必ず正になるようにしています。必要なステップ数は数の大きさに対してとてもゆっくりしか増えず、およそO(log n)です。

値を変更し、PythonをインストールせずにCodeUtilityオンラインPythonコンパイラで実行できます。

発展問題

下のヒントにしたがってコードを書き換えてみましょう。自分で変えて結果を確かめると、コードを読むだけよりずっと深く理解できます。

  1. 空のリスト、要素が1つだけのリスト、重複した値を含むリストで試す。
  2. 各ステップの後の状態を表示して、アルゴリズムの動きを観察する。
  3. 要素が100個、1,000個、10,000個のときの実行時間を測り、別の解き方と比べる。
Pythonコンパイラで実行 →

よくある間違い

余りの代わりに引き算を使う

引き算を繰り返しても同じ答えになりますが、2つの数の差が大きいと非常に遅くなります。

問題
while first != second:
    if first > second:
        first -= second
    else:
        second -= first
修正
while second:
    first, second = second, first % second

このレッスンを終えましたか?

学習済みにすると進み具合を記録できます。

チャレンジで練習する

このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。

すべてのチャレンジ