दो संख्याओं का GCD (महत्तम समापवर्तक) ज्ञात करना

परिचय

गणित में, ग्रेटेस्ट कॉमन डिवाइजर (GCD) वह सबसे बड़ी संभव पूर्णांक है जो दोनों पूर्णांकों को विभाजित करती है। शर्त यह है कि संख्याएँ शून्येतर होनी चाहिए।

हम दो संख्याओं का GCD ज्ञात करने के लिए यूक्लिडियन एल्गोरिदम का पालन करेंगे।

इनपुट और आउटपुट

इनपुट: दो संख्याएँ 51 और 34
आउटपुट: GCD है: 17

एल्गोरिदम

findGCD(a, b)
इनपुट: दो संख्याएँ a और b
आउटपुट: a और b का GCD

Begin
    यदि a = 0 या b = 0, तो
        0 लौटाएं
    यदि a = b, तो
        b लौटाएं
    यदि a > b, तो
        findGCD(a-b, b) लौटाएं
    अन्यथा
        findGCD(a, b-a) लौटाएं
End

उदाहरण (C++ कोड)

#include <iostream>
using namespace std;

int findGCD(int a, int b) {
    // मान लें a, b से बड़ा है
    if (a == 0 || b == 0)
        return 0; // चूंकि a और b 0 हैं, महत्तम भाजक भी 0 है
    if (a == b)
        return b; // जब दोनों संख्याएँ समान हों
    if (a > b)
        return findGCD(a-b, b);
    else
        return findGCD(a, b-a);
}

int main() {
    int a, b;
    cout << "Enter Two numbers to find GCD: ";
    cin >> a >> b;
    cout << "The GCD is: " << findGCD(a,b);
}

आउटपुट

Enter Two numbers to find GCD: 51 34
The GCD is: 17