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