C++である数が別の数のすべての素因数で割り切れるかどうかを判定する方法

問題の概要

2つの整数が与えられたとき、一方の数がもう一方の数のすべての素因数で割り切れるかどうかを判定します。

例として、ある数が 120 の場合、その素因数は {2, 3, 5} です。もう一方の数が 75 であれば、その素因数は {3, 5} となります。120 は 3 でも 5 でも割り切れるため、この場合の答えは「Yes」です。

アルゴリズムの考え方

この問題は、最大公約数（GCD）を利用することで効率的に解くことができます。手順は以下の通りです。

• もし相手の数が 1 であれば、素因数を一切持たないため、答えは常に true になります。
• それ以外の場合は、まず2つの数の GCD を求めます。
• GCD が 1 であれば、両者は互いに素（共素）であり、共通の素因数を持たないため、答えは false です。
• GCD が 1 より大きい場合、その GCD には最初の数 x をも割り切る素因数が含まれています。したがって、「y のすべての素因数が x を割り切る」ことは「y / GCD のすべての素因数が x を割り切る」ことと同値になります。
• そこで、ペア (x, y / GCD) に対して同じ判定を再帰的に適用していきます。

C++による実装例

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

bool isDivisible(int a, int b) {
    if (b == 1)
        return true;
    int gcd = __gcd(a, b);
    if (gcd == 1)
        return false;
    return isDivisible(a, b / gcd);
}

int main() {
    int a = 120, b = 75;
    if (isDivisible(a, b))
        cout << a << " can be divisible by all prime factors of " << b;
    else
        cout << a << " can NOT be divisible by all prime factors of " << b;
}

出力結果

120 can be divisible by all prime factors of 75

処理の流れを追ってみる

a = 120、b = 75 の場合の動作を確認してみましょう。

1. gcd(120, 75) = 15 → 15 ≠ 1 なので処理を継続
2. isDivisible(120, 75 / 15)、すなわち isDivisible(120, 5) を再帰呼び出し
3. gcd(120, 5) = 5 → 処理を継続
4. isDivisible(120, 5 / 5)、すなわち isDivisible(120, 1) を再帰呼び出し
5. b = 1 となったので true を返却

このように、GCD で割り進めることで素因数を一つずつ「消費」していき、最終的に b が 1 になれば、y のすべての素因数が a を割り切ることが保証されます。

補足：__gcd() について

__gcd() は GCC 固有の内部関数です。C++17 以降の環境では、標準ライブラリの std::gcd()（ヘッダー <numeric>）を使用することが推奨されます。移植性を重視する場合はこちらを採用しましょう。