C++-এ দুটি সংখ্যার HCF (GCD) বের করার প্রোগ্রাম

সমস্যা বিবরণ

দুটি সংখ্যা দেওয়া থাকলে, তাদের হাইএস্ট কমন ফ্যাক্টর (HCF) বা গ্রেটেস্ট কমন ডিভাইজার (GCD) বের করুন।

সমাধানের পদ্ধতি (ইউক্লিডিয়ান অ্যালগরিদম - রিকার্সিভ)

1. বেস কেস: a==0 বা b==0 → 0, a==b → a।
2. যদি a > b: gcd(a-b, b)
3. অন্যথায়: gcd(a, b-a)

নোট: মডুলো অপারেটর ব্যবহার করে আরও দ্রুত: gcd(a, b) = gcd(b, a%b)।

C++ কোড উদাহরণ

#include <stdio.h>

int gcd(int a, int b) {
    if (a == 0 || b == 0) return 0;
    if (a == b) return a;
    if (a > b) return gcd(a - b, b);
    return gcd(a, b - a);
}

int main() {
    int a = 98, b = 56;
    printf("GCD of %d and %d is %d ", a, b, gcd(a, b));
    return 0;
}

আউটপুট

GCD of 98 and 56 is 14

অপ্টিমাইজড ভার্সন (Modulo ব্যবহার)

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

জটিলতা

• সাবট্রাকশন মেথড: O(max(a,b))
• মডুলো মেথড: O(log min(a,b))