【C++】2つの数の公約数の個数を効率的に求めるプログラム

この記事では、2つの数に共通する約数（公約数）がいくつあるかを数える方法を解説します。すべての公約数を実際に列挙するのではなく、その「個数」だけを効率的に求めることが目的です。

例えば、12と24という2つの数を考えてみましょう。12と24の公約数は、1、2、3、4、6、12の6つです。したがって、答えは6となります。

アルゴリズムの考え方

すべての公約数を1つずつ調べるのは非効率です。ここで重要なのが、「2つの数aとbの公約数は、必ずgcd(a, b)（最大公約数）の約数になる」という性質です。つまり、gcd(a, b)の約数の個数を数えれば、それがそのまま公約数の個数になります。

さらに、約数の個数を数える際、1からgcdまで順番に調べる必要はありません。√gcd まで調べれば十分です。i が gcd の約数であれば、gcd / i もまた約数になるためです。これにより計算量を大幅に削減できます。

countCommonDivisor(a, b) の手順

begin
    count := 0
    gcd := aとbの最大公約数
    for i := 1 to √gcd, do
        if gcd が i で割り切れる, then
            if gcd / i = i, then
                count := count + 1
            else
                count := count + 2
            end if
        end if
    done
    return count
end

i が約数のとき、gcd / i も約数であるため、基本はカウントを2増やします。ただし、i が √gcd と一致する場合（gcdが完全平方数の場合）、同じ約数を二重に数えてしまうため、カウントは1だけ増やします。

C++での実装例

#include<iostream>
#include<cmath>
using namespace std;

int gcd(int a, int b) {
    if (a == 0)
        return b;
    return gcd(b % a, a); // ユークリッドの互除法
}

int countCommonDivisors(int a, int b) {
    int gcd_val = gcd(a, b); // aとbの最大公約数を取得
    int count = 0;
    for (int i = 1; i <= sqrt(gcd_val); i++) {
        if (gcd_val % i == 0) { // iがgcdの約数の場合
            if (gcd_val / i == i) // 重複カウントを避ける
                count += 1;
            else
                count += 2;
        }
    }
    return count;
}

int main() {
    int a = 12, b = 24;
    cout << "Total common divisors: " << countCommonDivisors(a, b);
}

実行結果

Total common divisors: 6

計算量の評価

このアルゴリズムでは、ユークリッドの互除法によるGCD計算が O(log(min(a, b)))、約数の個数のカウントが O(√gcd(a, b)) かかります。小さい方の数まで全て調べる O(min(a, b)) の素朴なアプローチと比べ、大きな数を扱う場合でも高速に動作するのが大きな利点です。