দুই সংখ্যার মহত্তম সাধারণ ভাজক (GCD) হলো সেই বৃহত্তম সংখ্যা যা উভয় সংখ্যাকে বিভাজ্য করে।
উদাহরণস্বরূপ: ৪৫ এবং ২৭-এর জন্য -
45 = 5 × 3 × 3 27 = 3 × 3 × 3
সুতরাং, GCD হলো ৯।
পদ্ধতি ১: ইউক্লিডিয়ান অ্যালগরিদম (রিকার্সিভ)
#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 = 105, b = 30;
cout << "GCD of " << a << " and " << b << " is " << gcd(a, b);
return 0;
}
আউটপুট
GCD of 105 and 30 is 15
gcd() একটি রিকার্সিভ ফাংশন। যদি b == 0 হয়, তবে a রিটার্ন করা হয়। অন্যথায়, ফাংশন নিজে আপনাকে b এবং a % b আর্গুমেন্ট দিয়ে কল করে।
পদ্ধতি ২: বিয়োগ পদ্ধতি (রিকার্সিভ)
#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 = 105, b = 30;
cout << "GCD of " << a << " and " << b << " is " << gcd(a, b);
return 0;
}
আউটপুট
GCD of 105 and 30 is 15
এই পদ্ধতিতে, যদি যেকোনো সংখ্যা ০ হয় তবে ০ রিটার্ন করা হয়। যদি দুটি সংখ্যা সমান হয়, তবে সেটিই GCD। বড় সংখ্যা থেকে ছোট সংখ্যা বিয়োগ করে রিকার্সিভভাবে কল করা হয় যতক্ষণ না দুটি সংখ্যা সমান হয়।
