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

はじめに

本記事では、Pythonを使って配列（リスト）内の2つ以上の数値から最大公約数（GCD：Greatest Common Divisor）を求める方法を解説します。

問題の概要

数値の配列が与えられ、そのすべての要素に共通する最大公約数を求めることが目的です。

3つ以上の数値のGCDは、「引数として渡されたすべての数値に共通する素因数の積」として定義できます。また、隣り合う2つの数値のGCDを繰り返し計算していくことでも求められます。

ここでは、後者のアプローチである「ペアごとのGCDを順番に計算する」方法を実装します。

アルゴリズムの流れ

• まず、リストの最初の2つの要素のGCDを計算します。
• 次に、その結果と3番目の要素の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

コードの解説

関数 findgcd は、ユークリッドの互除法を実装したものです。whileループの中で x と y を入れ替えながら剰余を計算し続け、y が0になった時点での x の値が最大公約数となります。

メイン処理では、リスト l の先頭2要素のGCDを求めた後、for ループを使って残りの要素に対して順番にGCDを更新していきます。この手法により、要素数がいくつあっても対応できる汎用的な実装になります。

まとめ

本記事では、Pythonを用いて配列内の複数の数値の最大公約数を求める方法を学びました。ユークリッドの互除法をベースに、ペアごとのGCDを逐次計算することで、シンプルかつ効率的に任意の個数の数値へ対応できることが確認できました。