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

このチュートリアルでは、C++を使って2つの数の最大公約数（GCD：Greatest Common Divisor、HCF：Highest Common Factor）を求めるプログラムについて解説します。

ここでは、2つの整数が与えられたときに、その両方を割り切れる最大の数（最大公約数）を計算することを目標とします。

プログラム例

#include <iostream>
using namespace std;
int gcd(int a, int b){
    if (a == 0)
        return b;
    if (b == 0)
        return a;
    if (a == b)
        return a;
    if (a > b)
        return gcd(a-b, b);
    return gcd(a, b-a);
}
int main(){
    int a = 98, b = 56;
    cout<<"GCD of "<<a<<" and "<<b<<" is "<<gcd(a, b);
    return 0;
}

出力

GCD of 98 and 56 is 14

アルゴリズムの解説

このプログラムは、減算を繰り返す方式のユークリッドの互除法を再帰的に実装したものです。処理の流れは以下の通りです。

• 一方の値が0になった場合、もう一方の値がそのまま最大公約数となるため、その値を返します。
• 両方の値が等しい場合、その値自体が最大公約数です。
• aがbより大きい場合は「a − b」を、そうでない場合は「b − a」を計算し、gcd関数を再帰的に呼び出して処理を続けます。

この例では、98と56の最大公約数は14であるため、「GCD of 98 and 56 is 14」という結果が出力されます。なお、この手法はシンプルで理解しやすい反面、数値が大きい場合には剰余演算（%）を使う標準的なユークリッドの互除法の方が効率的です。