C++で再帰やユークリッドの互除法を使わずに2つの数の最大公約数（HCF）を求める方法

最大公約数（HCF、GCDとも呼ばれます）は、通常「ユークリッドの互除法」を使えば簡単に計算できます。しかし、この記事では、ユークリッドの互除法や再帰的なアルゴリズムに頼らずに、GCD（HCF）を求める方法を紹介します。例として、16と24という2つの数を考えます。この2つの数の最大公約数は8です。

アルゴリズムの考え方

ここでのアプローチは非常にシンプルです。手順は以下のとおりです。

1. まず、2つの数のうち小さい方の値を取得します。
2. 大きい方の数が小さい方の数で割り切れる場合、その小さい方の数がそのままHCFとなります。
3. 割り切れない場合は、小さい方の数の半分（min / 2）から2まで順に値を減らしながら調べていき、現在の値が両方の数を割り切れた時点で、その値がHCFとなります。
4. どの値でも割り切れなかった場合は、1がHCFとなります。

この方法は直感的で理解しやすく、再帰呼び出しや剰余演算を繰り返すユークリッドの互除法とは異なるアプローチです。ただし、計算量はO(min(a, b))程度となるため、非常に大きな数を扱う場合はユークリッドの互除法の方が効率的である点に注意してください。

サンプルコード

#include <iostream>
using namespace std;
int gcd(int a, int b) {
   int min_num = min(a, b);
   if (a % min_num == 0 && b % min_num == 0)
   return min_num;
   for (int i = min_num / 2; i >= 2; i--) {
      if (a % i == 0 && b % i == 0)
      return i;
   }
   return 1;
}
int main() {
   int a = 16, b = 24;
   cout << "HCF: "<< gcd(a, b);
}

実行結果

HCF: 8

コードの解説

このプログラムでは、まずmin()関数を使って2つの数のうち小さい方をmin_numとして取得します。次に、min_numが両方の数を割り切れるかどうかを確認し、割り切れればその値を返します。割り切れない場合は、min_num / 2から2までループを回しながら、両方の数を割り切れる最初の値を探します。16と24の場合、小さい方の16を24が割り切れないため、8から順に調べていき、8が両方を割り切れるため8が結果として出力されます。