C++ Program for GCD of two numbers

C++ Program to find the GCD of two numbers

 

Here, in this section we will discuss GCD of two numbers in C++. GCD (Greatest Common Divisor) of two numbers is the largest number that divides both numbers.

Example : The GCD of 45 and 30 will be :

                   Factors of 45 are 3 X 3 X 5

                   Factors of 30 are 2 X 3 X 5

                   Common factors of 45 and 30 are : 3 X 5 , So the required GCD will be 15

 

GCD of two number in C++

Algorithm :

  • Take two inputs from the user and stare them in variable a and b.
  • To find GCD we define a function say gcd(int a, int b) which takes two parameters.
  • Now we recursively call this function, until b != 0.
  • During recursive calls we pass the parameter as a and a%b.
  • When b==0 then, the value of a stands for the required GCD of given two numbers.

C++ Program based on above algorithm

#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 first number :";
cin >> a ;

cout<<"\nEnter second number :";
cin >> b;

cout << "GCD of " << a << " and " << b << " is " << gcd (a, b);

return 0;
}
Output 

Enter first number : 48

Enter second number : 36

GCD of 48 and 36  is 12