C++でHCF（最大公約数）を反復処理で求めるプログラム

この記事では、C++を使ってHCF（最大公約数）を反復処理（ループ）で求めるプログラムについて解説します。

HCF（Highest Common Factor：最大公約数）とは、2つ以上の整数に共通する約数の中で最も大きいものを指します。ここでは、2つの整数が与えられたとき、再帰呼び出しを使わずに反復的な関数でHCFを計算することを目標とします。

アルゴリズムの考え方

この手法では、減算を繰り返すことでHCFを求めます。具体的な手順は以下の通りです。

1. 2つの数 a と b の大小を比較します。
2. a が b より大きければ、a から b を引きます。
3. b が a より大きければ、b から a を引きます。
4. a と b が等しくなるまでこの操作を繰り返します。
5. 両者が等しくなった時点の値がHCFとなります。

サンプルコード

#include <bits/stdc++.h>
using namespace std;

int get_HCF(int a, int b) {
    while (a != b) {
        if (a > b)
            a = a - b;
        else
            b = b - a;
    }
    return a;
}

int main() {
    int a = 60, b = 96;
    cout << get_HCF(a, b) << endl;
    return 0;
}

出力

12

コードの解説

この例では、60と96のHCFを計算しています。whileループの中で、大きい方の数から小さい方の数を引き続けることで、最終的に両者の値は12で一致します。これが60と96の最大公約数です。

なお、この減算法はロジックがシンプルで理解しやすい反面、数値が大きい場合は処理回数が増えて非効率になります。そのようなケースでは、剰余演算を利用したユークリッドの互除法を採用すると、より高速にHCFを求められます。用途や入力サイズに応じて適切な手法を選択するとよいでしょう。