C++で2つの数の最大公約数（GCD）を求めるプログラム

最大公約数（GCD）とは

最大公約数（GCD: Greatest Common Divisor）とは、2つの整数をどちらも割り切る正の整数のうち、最も大きい数のことです。プログラミングの基礎的なアルゴリズム問題としてよく取り上げられるテーマであり、分数の約分や暗号処理など、さまざまな場面で活用されます。

例として、45と27という2つの数を考えてみましょう。

45 = 5 × 3 × 3
27 = 3 × 3 × 3

両方の数に共通する素因数は「3 × 3」であるため、45と27の最大公約数は9となります。

方法1：ユークリッドの互除法による実装

2つの数の最大公約数を求める最も効率的な方法が「ユークリッドの互除法」です。以下にC++での実装例を示します。

サンプルコード

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

int main() {
    int a = 105, b = 30;
    cout << "GCD of " << a << " and " << b << " is " << gcd(a, b);
    return 0;
}

出力結果

GCD of 105 and 30 is 15

プログラムの解説

上記のプログラムでは、gcd()が再帰関数として定義されています。この関数はaとbの2つの引数を受け取り、処理の流れは以下の通りです。

• bが0になった場合、aが最大公約数であるため、aをmain()関数に返します。
• bが0でない場合は、bと「aをbで割った余り（a % b）」を新しい引数として、gcd()関数を再帰的に呼び出します。

該当するコード部分は以下の通りです。

int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

ユークリッドの互除法は、剰余を繰り返し計算することで高速に最大公約数を求められるため、計算量はO(log(min(a, b)))と非常に効率的です。

方法2：減算による再帰的な実装

次に、引き算を用いて最大公約数を求める別のプログラムを紹介します。

サンプルコード

#include<iostream>
using namespace std;

int gcd(int a, int b) {
    if (a == 0 || b == 0)
        return 0;
    else if (a == b)
        return a;
    else if (a > b)
        return gcd(a - b, b);
    else
        return gcd(a, b - a);
}

int main() {
    int a = 105, b = 30;
    cout << "GCD of " << a << " and " << b << " is " << gcd(a, b);
    return 0;
}

出力結果

GCD of 105 and 30 is 15

プログラムの解説

このプログラムでもgcd()は再帰関数として実装されています。引数はaとbの2つで、処理の流れは以下の通りです。

• aまたはbが0の場合、関数は0を返します。
• aとbが等しい場合、その値が最大公約数となるため、aを返します。
• aがbより大きい場合、aからbを引いた値（a - b）とbを引数として再帰的に呼び出します。
• bがaより大きい場合、aとbからaを引いた値（b - a）を引数として再帰的に呼び出します。

該当するコード部分は以下の通りです。

int gcd(int a, int b) {
    if (a == 0 || b == 0)
        return 0;
    else if (a == b)
        return a;
    else if (a > b)
        return gcd(a - b, b);
    else
        return gcd(a, b - a);
}

まとめ

2つの数の最大公約数を求める方法として、剰余演算を使うユークリッドの互除法と、減算を繰り返す再帰的な方法の2つを紹介しました。どちらもシンプルな実装ですが、減算方式は2つの数の差が大きい場合に再帰呼び出しの回数が増えて非効率になるため、実用上は剰余演算によるユークリッドの互除法が推奨されます。