दो संख्याओं का सबसे बड़ा सामान्य भाजक (GCD) उन दोनों को विभाजित करने वाली सबसे बड़ी संख्या है।
उदाहरण के लिए:मान लें कि हमारे पास दो संख्याएँ हैं जो 63 और 21 हैं।
63 = 7 * 3 * 3 21 = 7 * 3
तो, 63 और 21 का जीसीडी 21 है।
पुनरावर्ती यूक्लिड का एल्गोरिथ्म सकारात्मक पूर्णांक a और b की एक जोड़ी का उपयोग करके GCD की गणना करता है और b और a%b को शून्य तक लौटाता है।
पुनरावर्ती यूक्लिड एल्गोरिथम का उपयोग करते हुए दो संख्याओं की जीसीडी को खोजने का कार्यक्रम इस प्रकार दिया गया है -
उदाहरण
#include <iostream>
using namespace std;
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
int main() {
int a , b;
cout<<"Enter the values of a and b: "<<endl;
cin>>a>>b;
cout<<"GCD of "<< a <<" and "<< b <<" is "<< gcd(a, b);
return 0;
} आउटपुट
उपरोक्त कार्यक्रम का आउटपुट इस प्रकार है -
Enter the values of a and b: 105 30 GCD of 105 and 30 is 15
उपरोक्त कार्यक्रम में, gcd() एक पुनरावर्ती कार्य है। इसके दो पैरामीटर हैं यानी ए और बी। यदि b 0 के बराबर है, तो a मुख्य () फ़ंक्शन पर वापस आ जाता है। अन्यथा gcd() फ़ंक्शन स्वयं को b और a%b मानों के साथ पुनरावर्ती रूप से कॉल करता है। यह निम्नलिखित कोड स्निपेट द्वारा प्रदर्शित किया जाता है -
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
} मुख्य () फ़ंक्शन में, उपयोगकर्ता से a और b के मानों का अनुरोध किया जाता है। फिर gcd() फ़ंक्शन को कॉल किया जाता है और a और b के GCD का मान प्रदर्शित होता है। यह नीचे देखा गया है -
int main() {
int a , b;
cout<<"Enter the values of a and b: "<<endl;
cin>>a>>b;
cout<<"GCD of "<< a <<" and "<< b <<" is "<< gcd(a, b);
return 0;
}