C++ Program To Find GCD (Greatest Common Divisor ) Using Functions

In this tutorial, we will learn the logic behind finding the GCD of any two numbers by implementing functions in C++.

Program To Find GCD (Greatest Common Divisor ) Using Functions in C++

The Greatest Common Divisor (GCD) of two numbers is the largest number that divides both of them.

For example: Let’s say we have two numbers are 45 and 27.

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

So, the GCD of 45 and 27 is 9.

A program to find the GCD of two numbers is given as follows:-

#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

In the above program, gcd() is a recursive function. It has two parameters i.e. a and b. If b is greater than 0, then a is returned to the main() function. Otherwise, the gcd() function recursively calls itself with the values b and a%b.

Another program to find the GCD of two numbers is as follows ?

#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

In the above program, gcd() is a recursive function. It has two parameters i.e. a and b. If a or b is 0, the function returns 0. If a or b are equal, the function returns a. If a is greater than b, the function recursively calls itself with the values a-b and b. If b is greater than a, the function recursively calls itself with the values a and (b - a).

Conclusion

Here, in this tutorial, we have seen how to find the GCD of any two numbers with the help of functions.