GCD খুঁজে পেতে C++ প্রোগ্রাম

দুটি সংখ্যার সর্বশ্রেষ্ঠ সাধারণ ভাজক (GCD) হল বৃহত্তম সংখ্যা যা তাদের উভয়কে ভাগ করে।

উদাহরণস্বরূপ:ধরা যাক আমাদের দুটি সংখ্যা হল 45 এবং 27।

45 = 5 * 3 * 3
27 = 3 * 3 * 3

সুতরাং, 45 এবং 27 এর GCD হল 9।

দুটি সংখ্যার 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() একটি পুনরাবৃত্ত ফাংশন। এর দুটি পরামিতি রয়েছে যেমন a এবং b। যদি b 0-এর বেশি হয়, তাহলে a কে main() ফাংশনে ফিরিয়ে দেওয়া হয়। অন্যথায় gcd() ফাংশনটি পুনরাবৃত্তিমূলকভাবে b এবং a%b মানগুলির সাথে নিজেকে কল করে। এটি নিম্নলিখিত কোড স্নিপেট −

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

দুটি সংখ্যার GCD খুঁজে বের করার জন্য আরেকটি প্রোগ্রাম হল −

উদাহরণ

#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() একটি পুনরাবৃত্ত ফাংশন। এর দুটি পরামিতি রয়েছে যেমন a এবং b। a বা b 0 হলে, ফাংশনটি 0 প্রদান করে। a বা b সমান হলে, ফাংশনটি a প্রদান করে। a যদি b এর থেকে বড় হয়, ফাংশনটি recursively নিজেকে a-b এবং b মান দিয়ে কল করে। যদি b a এর থেকে বড় হয়, ফাংশনটি পুনরাবৃত্তভাবে a এবং (b - a) মানগুলির সাথে নিজেকে কল করে। এটি নিম্নলিখিত কোড স্নিপেট দ্বারা প্রদর্শিত হয়৷

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);
}