2つの整数の最大公約数（GCD）を求める方法｜ユークリッドの互除法をC++で解説

数学において、最大公約数（GCD：Greatest Common Divisor）とは、2つの整数をどちらも割り切ることができる整数のうち、最も大きいものを指します。なお、GCDを求める対象となる数はゼロ以外である必要があります。

本記事では、古典的かつ効率的な手法であるユークリッドの互除法（Euclidean Algorithm）を用いて、2つの数のGCDを求める方法を解説します。

入力と出力の例

まず、プログラムの動作イメージをつかむために、具体的な入力と出力の例を見てみましょう。

入力:
2つの数 51 と 34
出力:
GCDは: 17

この例では、51と34の両方を割り切れる最大の整数は17であるため、出力結果は17となります。

アルゴリズム

ユークリッドの互除法では、「大きい方の数から小さい方の数を引く」という操作を繰り返し、2つの数が等しくなった時点でその値がGCDであると判断します。アルゴリズムの擬似コードは以下の通りです。

findGCD(a, b)

入力: 2つの数 a と b。

出力: a と b の最大公約数。

Begin
    if a = 0 OR b = 0, then
        return 0
    if a = b, then
        return b
    if a > b, then
        return findGCD(a-b, b)
    else
        return findGCD(a, b-a)
End

アルゴリズムの流れ

1. どちらかが0の場合： a または b が0であれば、GCDは0として0を返します。
2. 2つの数が等しい場合： a と b が同じ値であれば、その値自体がGCDとなるため b を返します。
3. a が大きい場合： a から b を引いた値と b で再帰的に関数を呼び出します。
4. b が大きい場合： a と b から a を引いた値で再帰的に関数を呼び出します。

C++による実装例

それでは、上記のアルゴリズムを実際にC++で実装してみましょう。再帰呼び出しを使うことで、シンプルに記述できます。

#include<iostream>
using namespace std;

int findGCD(int a, int b) {    //aがbより大きいと仮定する
    if(a == 0 || b == 0)
        return 0;      //aとbが0の場合、最大公約数も0となる
    if(a == b)
        return b;      //2つの数が等しい場合
    if(a > b)
        return findGCD(a - b, b);
    else
        return findGCD(a, b - a);
}

int main() {
    int a, b;
    cout << "GCDを求める2つの数を入力してください: "; cin >> a >> b;
    cout << "GCDは: " << findGCD(a, b);
}

コードのポイント

• findGCD 関数は再帰的に自分自身を呼び出すことで、2つの数の差を繰り返し計算していきます。
• ベースケース（再帰の終了条件）は「どちらかが0」または「2つの数が等しい」場合です。
• main 関数では標準入力から2つの整数を受け取り、結果を出力します。

実行結果

GCDを求める2つの数を入力してください: 51 34
GCDは: 17

まとめ

このように、ユークリッドの互除法を使えば、剰余や複雑な計算を用いずとも、引き算と再帰だけで2つの整数の最大公約数を簡単に求めることができます。処理の効率化を図る場合は、引き算の代わりに剰余演算（%）を使う方法も一般的なので、ぜひ試してみてください。