再帰的ユークリッドの互除法で2つの数の最大公約数（GCD）を求めるC++プログラム

2つの数の最大公約数（GCD：Greatest Common Divisor）とは、その両方を割り切ることができる最大の数のことです。

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

63 = 7 × 3 × 3
21 = 7 × 3

この場合、63と21に共通する因数は7と3なので、GCDは次のようになります。

GCD = 7 × 3 = 21

再帰的ユークリッドの互除法とは

再帰的ユークリッドの互除法では、正の整数aとbのペアを受け取り、「b」と「a % b（aをbで割った余り）」を引数として自分自身を再帰的に呼び出し、bが0になった時点でaを返すことでGCDを求めます。

このアルゴリズムを使って2つの数のGCDを求める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, b;
    cout << "Enter the values of a and b: " << endl;
    cin >> a >> b;
    cout << "GCD of " << a << " and " << b << " is " << gcd(a, b);
    return 0;
}

実行結果

上記のプログラムを実行すると、次のような出力が得られます。

Enter the values of a and b: 105 30
GCD of 105 and 30 is 15

プログラムの解説

このプログラムの中核となるのが、再帰関数であるgcd()です。この関数はaとbという2つの引数を持ちます。bが0の場合はaをそのままmain()関数に返します。そうでない場合は、bと「a % b」を新しい引数として自分自身を再帰的に呼び出します。

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

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

一方、main()関数では、ユーザーからaとbの値を入力してもらい、その後gcd()関数を呼び出して、aとbのGCDの値を画面に表示します。

int main() {
    int a, b;
    cout << "Enter the values of a and b: " << endl;
    cin >> a >> b;
    cout << "GCD of " << a << " and " << b << " is " << gcd(a, b);
    return 0;
}

例えば入力が105と30の場合、gcd(105, 30) → gcd(30, 15) → gcd(15, 0) と再帰が進み、最終的に15が返されます。このように、ユークリッドの互除法は毎回余りを計算することで問題を小さくしていき、効率的にGCDを求めることができるのです。