数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程语言
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学学
生物学
数学
英语
经济学
心理学
社会学
服装研究
法律研究检查一个数是否被另一个数的所有质因数整除
假设有两个数。我们要检查一个数是否被第二个数的所有的质因子整除。假设一个数是 120。质因子是 {2, 3, 5}，另一个数是 75，这里质因子是 {3, 5}。因为 120 也被 3 和 5 整除，所以答案是肯定的。
如果一个数是 1，则它没有质因子，所以答案为 True。否则我们必须找到这两个数的最大公约数。如果最大公约数是 1，则它们是互质的。所以答案为 false。如果最大公约数 > 1，最大公约数中有质因子，它也整除 x（x 作为第一个数）。如果第二个数 y/GCD 有这样的唯一质因子，我们就有所有唯一的质因子 iff。我们必须使用递归找到成对 (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
更新于: 22-10-2019
418 浏览量
广告