2つ以上の数値（配列）の最大公約数（GCD）を求めるC++プログラム

2つの数の「公約数」とは、その両方の数を割り切ることができる数のことです。

例えば、12の約数は 1、2、3、4、6、12 です。18の約数は 1、2、3、6、9、18 です。したがって、12と18の共通の約数（公約数）は 1、2、3、6 となり、その中で最も大きいものが「最大公約数（GCD: Greatest Common Divisor）」と呼ばれます。数学では、2つの整数 a と b の最大公約数は gcd(a, b) と表記され、この場合 gcd(12, 18) = 6 となります。

最大公約数はさまざまな場面で重要な役割を果たします。例えば、2つの数の「最小公倍数（LCM: Least Common Multiple）」、すなわち両方の数に共通する倍数のうち最も小さい正の整数を求める際に利用できます。最小公倍数は次の式で計算できます。

LCM(a, b) = a × b ÷ GCD(a, b)

例えば、12と18の最小公倍数は 12 × 18 ÷ 6 = 36 となります。

問題

配列に含まれる複数の数値の最大公約数を求めます。

Input: 4, 10, 16, 14
Output: 2

説明

2つ以上の整数の最大公約数（GCD）とは、それらすべての数を余りなしで割り切ることができる最大の整数のことです。

複数の数のGCDを求める場合は、まず最初の2つの数のGCDを計算し、その結果と次の数のGCDを順番に求めていきます。これは gcd(a, b, c) = gcd(gcd(a, b), c) という性質（結合法則）が成り立つためです。

アルゴリズムのポイント

• GCDの計算には「ユークリッドの互除法」を使用します。「a を b で割った余りと b のGCDは、a と b のGCDに等しい」という性質を利用した効率的な手法です。
• 配列全体に対しては、初期値を最初の要素とし、残りの要素と順にGCDを更新していくことで答えが得られます。

サンプルコード

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    int temp;
    while (b > 0) {
        temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {
    int a[] = {4, 10, 16, 14};
    int n = 4;
    int r = a[0];
    for (int i = 1; i < n; i++) {
        r = gcd(r, a[i]);
    }
    cout << r << endl;
    return 0;
}

出力

2

このプログラムでは、gcd関数がユークリッドの互除法によって2数のGCDを返し、main関数内のループで配列の全要素に適用することで、4、10、16、14の最大公約数である 2 が出力されます。