检查一个数字是否可以被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
热门推荐
10 五一公司放假祝福语简短
11 追星女孩的祝福语简短
12 给长辈端午祝福语 简短
13 生日祝福语有诗意简短
14 团圆日祝福语简短
15 中秋商务祝福语简短最新
16 温暖文艺简短祝福语短句
17 男孩上学祝福语简短的
18 入住酒店文案祝福语简短