महत्तम समापवर्तक (GCD)
दो संख्याओं का GCD वह सबसे बड़ी संख्या है जो दोनों को विभाजित करती है।
उदाहरण
63 = 7 × 3 × 3 21 = 7 × 3 GCD(63, 21) = 21
यूक्लिड का रिकर्सिव एल्गोरिदम
एल्गोरिदम: gcd(a, b) = gcd(b, a % b) जब तक b शून्य न हो जाए।
C++ प्रोग्राम उदाहरण
#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 लौटाता है, अन्यथा खुद को (b, a%b) के साथ कॉल करता है।
मुख्य फ़ंक्शन
उपयोगकर्ता से दो संख्याएं लेता है और gcd() फ़ंक्शन कॉल करके परिणाम प्रदर्शित करता है।
समय जटिलता
O(log min(a, b)) - बहुत कुशल एल्गोरिदम।