このページではPythonで最大公約数（greatest common divisor）を求める方法について解説します。
math.gcd
標準ライブラリのmathにgcdという最大公約数を求める関数が用意されています。引数に最大公約数を求める２数を指定します。以下のコードでは36と156の最大公約数を求めて表示しています。
import math my_gcd = math.gcd(36, 156) print(my_gcd) # 12
（おそらく使われている方は少ないとは思いますが）Python3.5より前の古いPython3はmathではなくfractions.gcdとして実装されているので注意してください。
3つ以上の数の最大公約数を求める（Python3.9以降）
またPython3.9以降ではこの関数の引数に3つ以上の数を指定することが可能です。
import math # 6, 9, 12の最大公約数 my_gcd1 = math.gcd(6, 9, 12) print(my_gcd1) # 3 data = [144, 264, 84, 276] my_gcd2 = math.gcd(*data) print(my_gcd2) # 12
補足 ユークリッドの互除法
理解を深めるため最大公約数算出を自力で実装してみたい、という方向けに補足です。残念ながらmath.gcdはC言語で実装されているため参考にするのは難しいかもしれません。
https://github.com/python/cpython/blob/main/Modules/_decimal/_decimal.c
ですが、ユークリッドの互除法を使用すると再帰処理で簡単に最大公約数を求めるプログラムを作成することが可能なので紹介します。
ユークリッドの互除法
ユークリッドの互除法とは比較的古くから知られている最大公約数を求めるためのアルゴリズムの一つです。例えば、144と84の最大公約数を求める場合、以下のように剰余による除算を交互に繰り返し、剰余が0になったとき割った数が最大公約数となる、という方法になります。
例えば、144と84の最大公約数を求めたい場合、以下のように計算を繰り返します。
繰り返し処理であるためwhile等のループを使用してもいいのですが、再帰処理のほうが簡単にかけるかと思います。以下に実装例を示します。
ユークリッドの互除法の実装例
def gcd(a, b):
if a == 0:
return b
m = b % a
print(b, a, m)
return gcd(m, a)
my_gcd = gcd(144, 84)
print(my_gcd)
実行してみると被除数、除数、剰余が順に表示された後、結果が表示されます。
84 144 84 144 84 60 84 60 24 60 24 12 24 12 0 12
