【Python】math.gcdで最大公約数をスマートに求める
数学的な計算が必要なプログラムでは、複数の数値の「最大公約数」を求めたい場面が多々あります。Pythonでは標準ライブラリのmathモジュールを使うことで、複雑な計算式を書かずに一瞬で算出可能です。
1. 考え方：最大公約数（GCD）とは
最大公約数（Greatest Common Divisor）は、2つ以上の整数に共通する約数の中で、最も大きい数値のことです。分数の約分や、タイルの敷き詰め問題などのアルゴリズムで活用されます。
a = 12 (約数: 1, 2, 3, 4, 6, 12)
b = 8 (約数: 1, 2, 4, 8)
[ 判定ルール ]
・共通する約数（公約数）は 1, 2, 4
・その中で最大のもの → 4
b = 8 (約数: 1, 2, 4, 8)
[ 判定ルール ]
・共通する約数（公約数）は 1, 2, 4
・その中で最大のもの → 4
2. Pythonサンプルプログラム
math.gcd() 関数を使用します。自分でループを回して計算する必要がないため、コードが非常にシンプルになります。
-- coding: utf-8 --
import math
def main():
a = 12
b = 8
print(f"{a} と {b} の最大公約数を求めます。")
# math.gcd() で計算
result = math.gcd(a, b)
print(f"結果: {result}")
if name == "main":
main()
3. 実行結果
12 と 8 の最大公約数を求めます。
結果: 4
結果: 4
4. ステップアップ：より高度な数学関数
mathモジュールには、GCD以外にも便利な関数が用意されています。
- 最小公倍数（lcm）：Python 3.9以降では
math.lcm(a, b)で最小公倍数も求められます。 - 絶対値（fabs）：
math.fabs(x)で数値の絶対値を取得できます。
5. リストと組み合わせた使い分け
複数の数値（3つ以上）の最大公約数を求めたい場合、リストと組み合わせるのが効率的です。
| ケース | 実装方法 | メリット |
|---|---|---|
| 2つの数値 | math.gcd(a, b) |
最もシンプルで基本の書き方。 |
| 3つ以上の数値 | math.gcd(*list) |
可変長引数を使って一気に算出可能。 |
6. まとめ
最大公約数の計算は、アルゴリズムの基礎です。Pythonなら import math を一行書くだけで、正確かつ高速に答えを導き出せます。数学的な処理が必要な際は、まず math モジュールに便利な道具がないか探してみるのが上達の近道です！
PR
