Pythonで最大公約数（ユークリッドの互除法）

ユークリッドの互除法を使って2つの数の最大公約数を求める実装例です。コピペで動くコードと実行結果、処理の流れを確認できます。 下のコードはブラウザ内でそのまま実行できます。「実行エディタで開く」を押すと、progoのオンラインPython実行環境にコードが読み込まれ、その場で動作を確認できます。

サンプルコード

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

print(gcd(48, 18))
print(gcd(1071, 462))

ポイント解説

• %で剰余を求め繰り返し計算します。
• タプル代入a,b=b,a%bで更新します。
• 標準ライブラリのmath.gcdでも同じ結果になります。