C++ में जांचें कि कोई संख्या दूसरी संख्या के सभी अभाज्य भाजकों से विभाज्य है या नहीं

समस्या विवरण

दो संख्याएं a और b दी गई हैं। जांचें कि क्या a, b के सभी अभाज्य भाजकों से विभाज्य है।

उदाहरण: a=120 (भाजक: 2,3,5), b=75 (भाजक: 3,5) → 120, 3 और 5 से विभाज्य है → YES

एल्गोरिदम

1. यदि b=1 तो true (कोई अभाज्य भाजक नहीं)
2. GCD(a,b) निकालें
3. यदि GCD=1 तो false (सह-अभाज्य)
4. अन्यथा पुनरावर्ती रूप से जांचें: isDivisible(a, b/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;
    return 0;
}

आउटपुट

120 can be divisible by all prime factors of 75