দুটি সংখ্যার মহत्तম সাধারণ বিভাজক (GCD) হলো এমন সর্বোচ্চ সংখ্যা যা উভয় সংখ্যাকে ভাগ করে দেয়।
উদাহরণস্বরূপ: ধরি আমাদের দুটি সংখ্যা আছে ৬৩ এবং ২১।
63 = 7 × 3 × 3 21 = 7 × 3
সুতরাং, ৬৩ এবং ২১-এর GCD হলো ২১।
রিকারসিভ ইউক্লিড অ্যালগরিদম একটি জোড়া ধনাত্মক পূর্ণসংখ্যা a এবং b ব্যবহার করে GCD গণনা করে এবং b শূন্য হয় না পর্যন্ত b এবং a%b রিটার্ন করে।
রিকারসিভ ইউক্লিড অ্যালগরিদম ব্যবহার করে দুটি সংখ্যার 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, b;
cout << "Enter the values of a and b: " << endl;
cin >> a >> b;
cout << "GCD of " << a << " and " << b << " is " << gcd(a, b);
return 0;
}
আউটপুট
Enter the values of a and b: 105 30 GCD of 105 and 30 is 15
উপরোক্ত প্রোগ্রামে, gcd() একটি রিকারসিভ ফাংশন। এর দুটি প্যারামিটার আছে: a এবং b। যদি b ০-এর সমান হয়, তবে aকে main() ফাংশনে রিটার্ন করা হয়। অন্যথায়, gcd() ফাংশনটি নিজে কে b এবং a%b মান लेकर রিকারসিভলি কল করে। এটি নিচের কোড স্নিপেটে প্রদর্শিত হয়েছে:
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
main() ফাংশনে, a এবং b-এর মান ব্যবহারকারী থেকে অনুরোধ করা হয়। তারপর gcd() ফাংশনটি কল করা হয় এবং a ও b-এর GCD মান প্রদর্শন করা হয়। এটি নিচে দেখা যাচ্ছে:
int main() {
int a, b;
cout << "Enter the values of a and b: " << endl;
cin >> a >> b;
cout << "GCD of " << a << " and " << b << " is " << gcd(a, b);
return 0;
}
