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

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

最大公約数とは、2つの整数をどちらも割り切ることができる正の整数の中で、最も大きいものを指します。例えば、98と56の場合、両方を割り切れる最大の数は14となるため、最大公約数は14です。

アルゴリズムの考え方

ここでは再帰的な手法を用いて最大公約数を求めます。基本的な流れは以下のとおりです。

• どちらかの数が0の場合は、0を返します
• 2つの数が等しい場合は、その値が最大公約数となります
• aがbより大きい場合は、aからbを引いた値とbで再帰的に計算します
• それ以外の場合は、aとbからaを引いた値で再帰的に計算します

サンプルコード

#include <stdio.h>
// 再帰呼び出しでHCFを求める
int gcd(int a, int b){
    if (a == 0 || b == 0)
        return 0;
    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;
    printf("GCD of %d and %d is %d ", a, b, gcd(a, b));
    return 0;
}

実行結果

GCD of 98 and 56 is 14

補足：ユークリッドの互除法との関係

上記のコードは「減算による再帰」を使ったシンプルな実装ですが、数値が大きい場合には処理に時間がかかることがあります。より効率的に求めたい場合は、剰余演算（%）を用いたユークリッドの互除法を採用するのが一般的です。gcd(a, b) を gcd(b, a % b) に置き換えることで、再帰回数を大幅に減らすことができます。