GCD (Greatest Common Divisor) = দুটি সংখ্যা বিভাজ্য সর্বোচ্চ সংখ্যা। উদাহরণ: ৬৩ এবং ৪২-এর GCD = ২১।
পদ্ধতি ১: সাবট্রাকশন বেজড (Euclidean Algorithm - Subtraction Version)
#include <iostream>
using namespace std;
int gcd(int a, int b) {
if (a == 0 || b == 0)
return 0;
else if (a == b)
return a;
else if (a > b)
return gcd(a - b, b);
else
return gcd(a, b - a);
}
int main() {
int a = 63, b = 42;
cout << "GCD of " << a << " and " << b << " is " << gcd(a, b);
return 0;
}আউটপুট
GCD of 63 and 42 is 21
পদ্ধতি ২: মডুলো বেজড (Euclidean Algorithm - Standard)
#include <iostream>
using namespace std;
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
int main() {
int a = 63, b = 42;
cout << "GCD of " << a << " and " << b << " is " << gcd(a, b);
return 0;
}আউটপুট
GCD of 63 and 42 is 21
ব্যাখ্যা
পদ্ধতি ১ (Subtraction)
- বড় থেকে ছোট বিয়োগ করে রিকার্সন।
- যখন সমান হয়, তা GCD।
- দ্রুত নয়, অনেক রিকার্সিভ কল লাগে।
পদ্ধতি ২ (Modulo - Standard Euclidean)
gcd(a, b) = gcd(b, a % b)।- বহুত দ্রুত (O(log min(a,b)))।
- স্ট্যান্ডার্ড এবং প্রয়োগযোগ্য।
C++17: std::gcd(a, b) (<numeric>) লাইব্রেরি ফাংশন ব্যবহার করা যাবে।
