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
- 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
using namespace std;
int gcd (int a, int b)
if (b == 0)
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);
Enter first number : 48
Enter second number : 36
GCD of 48 and 36 is 12