Categories: Python

【Python】最大公約数と最小公倍数ついでに公約数を求める方法

この記事では、Pythonで最大公約数、および最小公倍数を取得する方法を解説します。ついでに公約数を求める方法も解説します。

公約数とは、二つ以上の整数に共通している約数のことを言います。約数については他の記事で解説しているのでそちらを参照してください。

Link約数を計算してみる

公倍数とは、二つ以上の整数に共通している倍数のことを言います。

それでは、最大公約数、および最小公倍数を取得する方法を見ていきましょう!!

最大公約数
- math.gcd()
- fractions.gcd()
最小公倍数
公約数
まとめ

最大公約数

最大公約数を求める関数は以下2つである。

math.gcd()
fractions.gcd() : Python 3.5 から非推奨

math.gcd()

Pythonのバージョンによって挙動が異なるのでそれぞれ見ていく。

Python 3.5 以降

math.gcd()は、Python 3.5 で追加されました。追加された当初は、引数で受け取った2つの整数の最大公約数を返す関数でした。

math.gcd(a, b)

例として最大公約数を取得してみます：

import math

print(math.gcd(8, 12))
# 4

Python 3.9 以降

Python 3.9 からmath.gcd()は、任意の数の引数を受け取るようになりました。受け取った任意の数の整数の最大公約数を返します。

math.gcd(*integers)

例として最大公約数を取得してみます：

import math

print(math.gcd(8, 12, 22))
# 2

fractions.gcd()

Python 3.4 以前では、fractions.gcd()を使っていた。fractions.gcd()は、引数で受け取った2つの整数の最大公約数を返す関数です。Python 3.5 から非推奨となります。

fractions.gcd(a, b)

例として最大公約数を取得してみます：

import fractions

print(fractions.gcd(8, 12))
# 4

最小公倍数

最小公倍数はmath.lcm()で取得することができます。この関数は Python 3.9 で追加されました。

math.lcm(*integers)

例として最小公倍数を取得してみます：

import math

print(math.lcm(8, 12))
# 24

それ以前は最小公倍数を求める関数が存在しなかったので自作関数を定義して使っていた。最小公倍数は、積 / 最大公約数で計算できるので以下のような感じの関数となる。

import math
from functools import reduce

def lcm(*integers):
    prod = 1
    for i in integers:
        prod *= i
    
    return prod // reduce(math.gcd, integer)

print(lcm(6, 7))
# 42

ちなみにfunctools.reduce()は、可変長引数に対応するために使用しています。

外部Linkreduce -- functools --- 高階関数と呼び出し可能オブジェクトの操作 — Python 3.11.5 ドキュメント

公約数

公約数は、約数を求めてその中から共通するものを探せば求めることができます。しかし、この方法では効率が悪いので最大公約数の約数を求めて公約数を割り出します。

import math

# 約数を求める関数
def divisors(n: int) -> list[int]:
    result = []
    root = int(n**0.5)
    for i in range(1, root + 1):
        if n % i == 0:
            result.append(i)
            b = n // i
            if root == b:
                break
            result.append(b)
    return sorted(result)

# 公約数を求める関数
def common_divisor(*integers):
    return divisors(math.gcd(*integers))


print(common_divisor(32, 16, 48, 640))
# [1, 2, 4, 8, 16]