মৌলিক ইউক্লিডীয় অ্যালগরিদমের জন্য সি প্রোগ্রাম?

এখানে আমরা দুটি সংখ্যার GCD বের করতে ইউক্লিডীয় অ্যালগরিদম দেখব। ইউক্লিডীয় অ্যালগরিদম ব্যবহার করে GCD (গ্রেটেস্ট কমন ডিভাইজার) সহজেই পাওয়া যায়। দুটি ভিন্ন পদ্ধতি আছে. একটি পুনরাবৃত্তিমূলক, আরেকটি পুনরাবৃত্তিমূলক। এখানে আমরা পুনরাবৃত্ত ইউক্লিডীয় অ্যালগরিদম ব্যবহার করতে যাচ্ছি।

অ্যালগরিদম

ইউক্লিডীয় অ্যালগরিদম(a, b)

begin
   if a is 0, then
      return b
   end if
   return gcd(b mod a, a)
end

উদাহরণ

#include<iostream>
using namespace std;
int euclideanAlgorithm(int a, int b) {
   if (a == 0)
      return b;
   return euclideanAlgorithm(b%a, a);
}
main() {
   int a, b;
   cout << "Enter two numbers: ";
   cin >> a >> b;
   cout << "GCD " << euclideanAlgorithm(a, b);
}

আউটপুট

Enter two numbers: 12 16
GCD 4