আমরা জানি, HCF বা GCD সহজে ইউক্লিডিয়ান অ্যালগরিদম দিয়ে বের করা যায়। কিন্তু এখানে আমরা দেখব কিভাবে ইউক্লিডিয়ান অ্যালগরিদম বা কোনো রিকারসিভ অ্যালগরিদম ব্যবহার না করেই GCD বা HCF বের করা যায়। ধরুন দুটি সংখ্যা আছে ১৬ এবং ২৪। এদের GCD হল ৮।
এখানে পদ্ধতিটি খুব সহজ। যদি দুটি সংখ্যার বড়টি ছোটটির দ্বারা বিভাজ্য হয়, তবে সেটিই HCF, অন্যথায় (ছোটটি / ২) থেকে ১ পর্যন্ত, যদি বর্তমান উপাদান দুটি সংখ্যাকেই ভাগ করে, তবে সেটিই HCF।
C++ প্রোগ্রাম উদাহরণ
#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);
return 0;
}
আউটপুট
HCF: 8
