আমরা জানি, ইউক্লিডীয় অ্যালগরিদম ব্যবহার করে 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
