ある数がC++の別の数のすべての素数除数で割り切れるかどうかを確認します

2つの数字があるとします。数がすべての素因数で割り切れるか、2番目の数で割り切れるかどうかを確認する必要があります。数が120であると仮定します。素因数は{2、3、5}、別の数は75、ここでは素因数は{3、5}です。 120も3と5で割り切れるので、決定は「はい」です。

1つの数が1の場合、素数の約数がないため、答えはTrueです。それ以外の場合は、これら2つの数値のGCDを見つける必要があります。 GCDが1の場合、それらは互いに素です。したがって、答えは誤りです。 GCDが>1の場合、GCDには素数除数が含まれます。これはxも除算します（xを最初の数として）。 2番目の数y/GCDがそのような一意の素数除数を持っている場合、すべての一意の素数除数がある場合。再帰を使用してペア（x、y / GCD）の一意性を見つける必要があります。

例

#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