हम जानते हैं कि HCF या GCD की गणना यूक्लिडियन एल्गोरिदम का उपयोग करके आसानी से की जा सकती है। लेकिन यहां हम देखेंगे कि बिना यूक्लिडियन एल्गोरिदम या किसी रिकर्सिव एल्गोरिदम के GCD या HCF कैसे उत्पन्न करें। मान लीजिए दो संख्याएं 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