检查一个数字是否可以被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 婚前女儿生日祝福语简短