資料結構
網路
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 瀏覽量
廣告