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

本記事では、2つの数の最大公約数（GCD: Greatest Common Divisor）を求めるための「ユークリッドの互除法」について解説します。ユークリッドの互除法を利用すれば、GCDを簡単かつ効率的に計算することが可能です。実装方法には大きく分けて反復型（ループ処理）と再帰型の2つのアプローチがありますが、ここでは再帰的なユークリッドの互除法を取り上げます。

アルゴリズムの考え方

ユークリッドの互除法は、「2つの数のGCDは、一方を他方で割った余りと小さい方の数のGCDに等しい」という性質を利用します。具体的な流れは以下のとおりです。

• a が 0 の場合、b がそのまま GCD となるため b を返す
• それ以外の場合は、b を a で割った余りと a を引数として、自分自身を再帰的に呼び出す
• 余りが徐々に小さくなっていき、最終的に GCD が求まる

疑似コード：EuclideanAlgorithm(a, b)

begin
    if a is 0, then
        return b
    end if
    return gcd(b mod a, a)
end

C++による実装例

#include<iostream>
using namespace std;

// ユークリッドの互除法によりGCDを求める再帰関数
int euclideanAlgorithm(int a, int b) {
    if (a == 0)                          // a が 0 なら b が GCD
        return b;
    return euclideanAlgorithm(b % a, a); // 余りと a で再帰呼び出し
}

main() {
    int a, b;
    cout << "Enter two numbers: ";       // 2つの数値を入力
    cin >> a >> b;
    cout << "GCD " << euclideanAlgorithm(a, b);
}

実行結果

Enter two numbers: 12 16
GCD 4

上記の例では、12 と 16 を入力しています。16 を 12 で割ると余りは 4、次に 12 を 4 で割ると余りは 0 となるため、GCD は 4 と出力されます。

計算量について

ユークリッドの互除法の計算量は O(log(min(a, b))) であり、非常に高速なアルゴリズムです。入力値が大きくなっても少ないステップ数でGCDを求められるため、競技プログラミングや実務でも広く利用されています。