C++で中学校的手法（素因数分解）を使って2つの数の最大公約数（GCD・HCF）を求めるプログラム

この記事では、中学校で習う「素因数分解」の手法（ミドルスクール・プロシージャ／Middle School Procedure）を使って、2つの整数の最大公約数（GCD：Greatest Common Divisor、HCF：Highest Common Factor）を求めるC++プログラムを紹介します。

2つの整数が与えられたとき、それぞれを素因数分解し、共通する素因数のうち指数（べき乗）が小さい方を掛け合わせることで最大公約数を求めるのが、この手法の基本的な考え方です。

中学校的手法（Middle School Procedure）とは？

中学校の数学では、最大公約数を求めるときに次のような手順を学びます。

1. 2つの整数をそれぞれ素因数分解する。
2. 両方に共通して現れる素因数を取り出す。
3. 共通する素因数ごとに、指数が小さい方（より少ない個数）を掛け合わせる。

例えば 10 と 15 の場合、10 = 2 × 5、15 = 3 × 5 と分解できるため、共通する素因数は 5 のみとなり、GCD(10, 15) = 5 となります。

アルゴリズムの流れ

1. 与えられた2つの整数 m と n をそれぞれ素因数分解し、「素因数」と「その指数」を構造体に保存します。
2. 2つの素因数分解の結果を先頭から比較しながら走査します。
3. 同じ素因数が見つかったら、指数が小さい方の値を結果に掛け合わせます。
4. 片方の走査が終わった時点での累積値が最大公約数となります。

C++による実装例

#include <bits/stdc++.h>
#define MAXFACTORS 1024
using namespace std;

// 素因数分解の結果を格納する構造体
typedef struct {
    int size;
    int factor[MAXFACTORS + 1];
    int exponent[MAXFACTORS + 1];
} FACTORIZATION;

// 素因数分解を行う関数
void FindFactorization(int x, FACTORIZATION* factorization) {
    int i, j = 1;
    int n = x, c = 0;
    int k = 1;
    factorization->factor[0] = 1;
    factorization->exponent[0] = 1;
    for (i = 2; i <= n; i++) {
        c = 0;
        while (n % i == 0) {
            c++;
            n = n / i;
        }
        if (c > 0) {
            factorization->exponent[k] = c;
            factorization->factor[k] = i;
            k++;
        }
    }
    factorization->size = k - 1;
}

// 素因数分解の結果を表示する関数
void DisplayFactorization(int x, FACTORIZATION factorization) {
    int i;
    cout << "Prime factor of " << x << " = ";
    for (i = 0; i <= factorization.size; i++) {
        cout << factorization.factor[i];
        if (factorization.exponent[i] > 1)
            cout << "^" << factorization.exponent[i];
        if (i < factorization.size)
            cout << "*";
        else
            cout << "\n";
    }
}

// 中学校的手法によるGCDの計算
int gcdMiddleSchoolProcedure(int m, int n) {
    FACTORIZATION mFactorization, nFactorization;
    int r, mi, ni, i, k, x = 1, j;
    FindFactorization(m, &mFactorization);
    DisplayFactorization(m, mFactorization);
    FindFactorization(n, &nFactorization);
    DisplayFactorization(n, nFactorization);
    int min;
    i = 1;
    j = 1;
    while (i <= mFactorization.size && j <= nFactorization.size) {
        if (mFactorization.factor[i] < nFactorization.factor[j])
            i++;
        else if (nFactorization.factor[j] < mFactorization.factor[i])
            j++;
        else {
            min = mFactorization.exponent[i] > nFactorization.exponent[j] ? nFactorization.exponent[j] : mFactorization.exponent[i];
            x = x * mFactorization.factor[i] * min;
            i++;
            j++;
        }
    }
    return x;
}

int main() {
    int m = 10, n = 15;
    int result = gcdMiddleSchoolProcedure(m, n);
    cout << "GCD(" << m << ", " << n << ") = " << result << endl;
    return 0;
}

実行結果

Prime factor of 10 = 1*2*5
Prime factor of 15 = 1*3*5
GCD(10, 15) = 5

コードのポイント

• FACTORIZATION構造体：素因数（factor）とその指数（exponent）、および要素数（size）を保持します。
• FindFactorization関数：2から順に割り切れるかを試していき、素因数と指数を記録します。
• DisplayFactorization関数：素因数分解の結果を「1*2*5」のような形式で出力します。
• gcdMiddleSchoolProcedure関数：2つの素因数分解結果をマージする要領で、共通する素因数の最小指数を掛け合わせてGCDを求めます。

計算量について

この手法では、素因数分解に各数につき O(n)（√n まで試せばよいため O(√n) に改善可能）、共通素因数のマージに O(log m + log n) の時間がかかります。ユークリッドの互除法（O(log min(m, n))）と比べると効率は劣りますが、最大公約数の数学的な性質をそのままプログラムに落とし込んだ、非常に教育的なアルゴリズムといえます。

なお、競技プログラミングや実務では、ユークリッドの互除法やC++17以降の標準ライブラリ std::gcd を使うのが一般的です。本記事の手法は、素因数分解と最大公約数の関係を深く理解するための良い教材として活用できます。