Pythonでリスト内の全要素の最大公約数（GCD）を求める方法

Pythonでは、mathモジュールのgcd()関数を活用することで、リスト内のすべての整数に共通する最大公約数（GCD：Greatest Common Divisor）を簡単に求めることができます。

例えば、リスト nums = [15, 81, 78] が与えられた場合、15・81・78 のすべてを割り切れる最大の正の整数は 3 であるため、出力結果は 3 になります。

解法のアプローチ

この問題は、以下の手順で解決できます。

• リストの要素数が1つだけの場合は、その要素をそのまま返します。
• まず、最初の2つの要素 nums[0] と nums[1] の最大公約数を計算し、変数 div に格納します。
• 要素数が2つだけであれば、この時点で div を返して終了します。
• 3つ目以降の要素については、ループ処理で順番に div と各要素の最大公約数を計算していきます。
• 計算途中で div が 1 になった場合は、それ以上大きくなることはないため、即座に 1 を返して処理を打ち切ると効率的です。
• 最後に残った div の値が、リスト全体の最大公約数となります。

実装コード

以下に、実際のPythonコードの実装例を示します。

from math import gcd

def solve(nums):
    if len(nums) == 1:
        return nums[0]

    div = gcd(nums[0], nums[1])

    if len(nums) == 2:
        return div

    for i in range(1, len(nums) - 1):
        div = gcd(div, nums[i + 1])
        if div == 1:
            return div

    return div

nums = [15, 81, 78]
print(solve(nums))

入力

[15, 81, 78]

出力

3

補足：より簡潔な書き方

Python 3.9以降では、math.gcd() が複数の引数を受け取れるようになったため、以下のようにfunctools.reduceやアンパックを使ってより簡潔に記述することも可能です。

from math import gcd

nums = [15, 81, 78]
print(gcd(*nums))  # 出力: 3

このように、最大公約数の性質「gcd(a, b, c) = gcd(gcd(a, b), c)」を利用すれば、任意の個数の整数に対して柔軟に対応できます。