【C++入門】2つの数の最大公約数（GCD）を求めるプログラムの書き方

最大公約数（GCD：Greatest Common Divisor）とは、2つの整数に共通する約数の中で最も大きい数のことです。まずは「公約数」という概念から確認していきましょう。

公約数と最大公約数とは

ある数の約数とは、その数を余りなく割り切ることができる整数のことです。例として、12と18の約数を見てみます。

• 12の約数：1, 2, 3, 4, 6, 12
• 18の約数：1, 2, 3, 6, 9, 18

この両方に共通して現れる数、すなわち公約数は「1, 2, 3, 6」です。そして、その中で最も大きい「6」が最大公約数となります。

数学では、2つの整数 a と b の最大公約数を (a, b) という記号で表すのが一般的です。したがって、(12, 18) = 6 と書けます。

最大公約数が重要な理由

最大公約数はさまざまな場面で活用されます。代表的な例が最小公倍数（LCM）の計算です。最小公倍数とは、2つの数のどちらの倍数にもなる最小の正の整数であり、次の式で求められます。

最小公倍数 = a × b ÷ 最大公約数

例えば、12と18の最小公倍数は以下のように計算できます。

12 × 18 ÷ (12, 18) = 216 ÷ 6 = 36

問題の定義

今回作成するプログラムでは、与えられた2つの整数について、両方の数を余りなしで割り切ることができる整数（＝公約数）をすべて出力します。

Input: a = 10, b = 20
Output: 1 2 5 10
// 10と20の公約数はすべて 1, 2, 5, 10

C++での実装例

以下のコードは、1から小さい方の数まで順番に調べ、両方の数を割り切れる値だけを出力するシンプルな実装です。

#include <iostream>
using namespace std;
int main() {
    int n1, n2, i;
    n1 = 10;
    n2 = 20;
    for(i = 1; i <= n1 && i <= n2; ++i) {
        if(n1 % i == 0 && n2 % i == 0) {
            cout << i << "\t";
        }
    }
}

プログラムの仕組み

1. forループで変数 i を1から、n1 と n2 のうち小さい方の値まで順に増やしていきます。
2. 各 i について、「n1 % i == 0」かつ「n2 % i == 0」、つまり両方の数を割り切れるかどうかを剰余演算子（%）で判定します。
3. 条件を満たした i が公約数なので、タブ区切りで出力します。

この例では、10と20の公約数である「1, 2, 5, 10」が出力され、その中で最大の「10」が最大公約数であることが分かります。

補足：効率的な求め方（ユークリッドの互除法）

上記の方法は計算量が O(min(a, b)) となるため、大きな数を扱う場合は非効率です。実務ではユークリッドの互除法を使うのが一般的で、O(log(min(a, b))) で高速に最大公約数を求められます。

int gcd(int a, int b) {
    while(b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

まずは本記事のシンプルな全探索による実装で仕組みを理解し、慣れてきたらユークリッドの互除法にも挑戦してみてください。