Pythonで複数の数値や配列の最大公約数（GCD）を求める方法

本記事では、以下の問題に対する解決策について詳しく解説します。

問題の概要

与えられた数値の配列から、それらすべての最大公約数（GCD）を求める必要があります。

アプローチ

2つより多い数値の最大公約数を求める場合、GCDは引数として渡されたすべての数値に共通する素因数の積と等しくなります。これは数学的な定義に基づく方法ですが、実装がやや複雑になります。

もう一つの方法として、2つの数値ずつペアでGCDを繰り返し計算するという手法があります。具体的には、最初の2つの数値のGCDを求め、その結果と次の数値のGCDを計算し、これを配列の最後まで繰り返します。

本記事では、後者のアプローチを実装していきます。

実装例

def findgcd(x, y):
    while(y):
        x, y = y, x % y
    return x

l = [22, 44, 66, 88, 99]
num1 = l[0]
num2 = l[1]
gcd = findgcd(num1, num2)
for i in range(2, len(l)):
    gcd = findgcd(gcd, l[i])
print("gcd is: ", gcd)

実行結果

gcd is: 11

コードの解説

このプログラムのポイントを順番に見ていきましょう。

GCD計算関数「findgcd」

関数 findgcd(x, y) では、ユークリッドの互除法を使用しています。x % y の剰余を繰り返し計算することで、効率的に最大公約数を導き出せます。ループは y が0になった時点で終了し、その時点の x がGCDとなります。

配列への適用

まず、リスト l の先頭2要素（22と44）のGCDを初期値として計算します。その後、for ループを使って、残りの要素（66、88、99）を1つずつ順に処理し、直前のGCDと新たな要素のGCDを繰り返し求めていきます。

最終的に得られる結果は11です。実際、22、44、66、88、99のすべてに共通する最大の約数は11であるため、正しい結果が得られていることが確認できます。

なお、このプログラムでは変数や関数はすべてグローバルスコープで宣言されています。

まとめ

本記事では、ユークリッドの互除法をベースに、ペアごとのGCD計算を繰り返し適用することで、任意の個数の数値や配列全体の最大公約数を効率的に求める方法を学びました。この手法はシンプルでありながら計算量も少なく、実用的な場面で広く活用できます。