检查一个数字是否可以被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 公司28 周年祝福语简短
17 治愈语句祝福语大全简短
18 动心的生日祝福语简短