দুটি সংখ্যার GCD বের করা (Find GCD of two numbers)

গণিতে, সর্বোচ্চ সাধারণ ভাজক (GCD) হল বৃহত্তম সম্ভাব্য পূর্ণসংখ্যা, যা দুটি পূর্ণসংখ্যাকে বিভাজ্য করে। শর্ত হল সংখ্যাগুলো শূন্য নয় হতে হবে।

দুটি সংখ্যার GCD বের করার জন্য ইউক্লিডিয়ান অ্যালগরিদম অনুসরণ করব।

ইনপুট এবং আউটপুট

ইনপুট: দুটি সংখ্যা ৫১ এবং ৩৪ আউটপুট: GCD হল: ১৭

অ্যালগরিদম

findGCD(a, b)

ইনপুট: দুটি সংখ্যা a এবং b।

আউটপুট: a এবং b-এর GCD।

শুরু 
  যদি a = 0 অথবা b = 0, তবে 
    0 ফেরত দিন 
  যদি a = b, তবে 
    b ফেরত দিন 
  যদি a > b, তবে 
    findGCD(a-b, b) ফেরত দিন 
  অন্যথায় 
    findGCD(a, b-a) ফেরত দিন 
শেষ

উদাহরণ

#include<iostream> using namespace std; int findGCD(int a, int b) {   //a, b থেকে বড় ধরে নেওয়া হল   if(a == 0 || b == 0)     return 0;     //যেহেতু a এবং b ০, তাই সর্বোচ্চ ভাজকও ০   if(a==b)     return b;     //যখন দুটি সংখ্যা সমান   if(a>b)     return findGCD(a-b, b);   else     return findGCD(a, b-a); } int main() {   int a, b;   cout << "Enter Two numbers to find GCD: "; cin >> a >> b;   cout << "The GCD is: " << findGCD(a,b); }

আউটপুট

Enter Two numbers to find GCD: 51 34 The GCD is: 17