দুটি সংখ্যার সর্বশ্রেষ্ঠ সাধারণ ভাজক (GCD) হল সবচেয়ে বড় সংখ্যা যা তাদের উভয়কে ভাগ করে।
উদাহরণস্বরূপ:ধরা যাক আমাদের দুটি সংখ্যা আছে যেগুলি হল 63 এবং 21৷
৷63 = 7 * 3 * 3 21 = 7 * 3
সুতরাং, 63 এবং 21 এর GCD হল 21।
পুনরাবৃত্ত ইউক্লিডের অ্যালগরিদম একজোড়া ধনাত্মক পূর্ণসংখ্যা 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 0 এর সমান হয়, তাহলে a প্রধান() ফাংশনে ফিরে আসবে। অন্যথায় 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;
} 