जैसा कि हम जानते हैं, यूक्लिडियन एल्गोरिथम का उपयोग करके एचसीएफ या जीसीडी की गणना आसानी से की जा सकती है। लेकिन यहां हम देखेंगे कि यूक्लिडियन एल्गोरिथम, या किसी पुनरावर्ती एल्गोरिथम का उपयोग किए बिना जीसीडी या एचसीएफ कैसे उत्पन्न करें। मान लीजिए कि दो संख्याएँ 16 और 24 के रूप में मौजूद हैं। इन दोनों की GCD 8 है।
यहाँ दृष्टिकोण सरल है। यदि इन दोनों की बड़ी संख्या छोटी संख्या से विभाज्य है, तो वह HCF है, अन्यथा (छोटा / 2) से 1 तक, यदि वर्तमान तत्व दोनों संख्याओं को विभाजित करता है, तो वह HCF है।
उदाहरण
#include <iostream>
using namespace std;
int gcd(int a, int b) {
int min_num = min(a, b);
if (a % min_num == 0 && b % min_num == 0)
return min_num;
for (int i = min_num / 2; i >= 2; i--) {
if (a % i == 0 && b % i == 0)
return i;
}
return 1;
}
int main() {
int a = 16, b = 24;
cout << "HCF: "<< gcd(a, b);
} आउटपुट
HCF: 8