मान लीजिए कि दो संख्याएँ हैं। हमें यह जांचना है कि कोई संख्या सभी अभाज्य गुणनखंडों से विभाज्य है या दूसरी संख्या से। मान लीजिए एक संख्या 120 है। अभाज्य गुणनखंड {2, 3, 5} हैं, दूसरी संख्या 75 है, यहां अभाज्य गुणनखंड {3, 5} हैं। चूँकि 120, 3 और 5 से भी विभाज्य है, तो निर्णय हाँ है।
यदि एक संख्या 1 है, तो इसका कोई अभाज्य भाजक नहीं है, इसलिए उत्तर सत्य है। नहीं तो हमें इन दोनों संख्याओं की 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