Giả sử có hai số. Chúng ta phải kiểm tra xem một số có chia hết cho tất cả các thừa số nguyên tố hay số thứ hai hay không. Giả sử một số là 120. Các thừa số nguyên tố là {2, 3, 5}, một số khác là 75, ở đây các thừa số nguyên tố là {3, 5}. Vì 120 cũng chia hết cho 3 và 5 nên quyết định là có.
Nếu một số là 1, thì nó không có ước nguyên tố, vì vậy câu trả lời là Đúng. Nếu không ta phải tìm GCD của hai số này. Nếu GCD là 1 thì chúng là đồng nguyên tố. Vì vậy, câu trả lời là sai. Nếu GCD> 1, thì GCD chứa ước nguyên tố, chia cũng x (x là số đầu tiên). Nếu chúng ta có tất cả ước số nguyên tố duy nhất thì số thứ hai y / GCD có ước số nguyên tố duy nhất như vậy. Chúng ta phải tìm tính duy nhất cho cặp (x, y / GCD) bằng cách sử dụng đệ quy.
Ví dụ
#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;
} Đầu ra
120 can be divisible by all prime factors of 75