检查一个数字是否可以被C ++中另一个数字的所有质数除以

假设有两个数字。我们必须检查一个数字是否可以被所有素数或第二个数整除。假设数字为120。素数为{2，3，5}，另一个数为75，此处素数为{3，5}。由于120也可以被3和5整除，因此决定为是。

如果一个数字为1，则没有质数，因此答案为True。否则，我们必须找到这两个数字的GCD。如果GCD为1，则它们是互质的。所以答案是错误的。如果GCD> 1，则GCD包含质数除数，该质数也将x除（x为第一个数字）。如果我们拥有所有唯一的除数，那么第二个数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