检查一个数字是否可以被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
热门推荐
1 训练狗狗基础
2 怎么训练狗狗笑
3 怎么训练狗狗卧下
4 上海狗狗训练基地
5 训练狗狗排便
6 狗狗基础训练
8 如何训练狗狗装死
9 狗狗站姿训练
10 狗狗训练用品
11 训练狗狗吧
12 狗狗要怎么训练
13 怎么训练狗狗玩球
14 训练狗狗唤回
15 狗狗训练躺下
16 狗狗训练指令
17 狗狗的训练技巧
18 狗狗不好训练