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

問題概要

正の整数からなるリスト nums が与えられたとき、リスト内のすべての数値を割り切ることができる最大の正の整数、すなわち「最大公約数（GCD）」を求めます。

例えば、入力が [14, 28, 70, 56] の場合、これらすべての数を割り切れる最大の数は 14 となるため、出力は 14 になります。

解法のアプローチ

この問題は、数学における次の性質を利用すると簡単に解けます。

gcd(a, b, c) = gcd(gcd(a, b), c)

つまり、リスト全体の最大公約数は、要素を順番に処理しながらGCDを累積的に計算していくことで求められます。具体的な手順は以下の通りです。

• 変数 ans をリストの最初の要素で初期化する
• リスト内の各要素 x について、ans を ans と x の最大公約数に更新する
• 最終的な ans の値を返す

実装例

Pythonでは標準ライブラリの math.gcd() 関数を使うことで、最大公約数を簡単に計算できます。以下が実際のコードです。

import math

class Solution:
    def solve(self, nums):
        ans = nums[0]
        for x in nums:
            ans = math.gcd(ans, x)
        return ans

ob = Solution()
print(ob.solve([14, 28, 70, 56]))

入力

[14, 28, 70, 56]

出力

14

別の書き方：functools.reduce を使う方法

functools.reduce() を組み合わせると、同じ処理をより簡潔に記述できます。

import math
from functools import reduce

nums = [14, 28, 70, 56]
print(reduce(math.gcd, nums))  # 出力: 14

なお、Python 3.9 以降では math.gcd(*nums) のように複数の引数を直接渡すことも可能です。

まとめ

リスト内の複数の数値の最大公約数を求めるには、math.gcd() をループや reduce() と組み合わせるのが効率的です。どちらの方法でも計算量は要素数に対して線形程度に収まり、大量のデータでも高速に処理できます。