GCD of two numbers and its application...

The greatest common divisor (gcd) of two numbers is the largest positive integer that divides both numbers without leaving a remainder. The gcd can be found using the Euclidean algorithm

GCD is useful in cases when you want different amounts of things to be arranged in the same number of order. 

For example there are 32 soldiers and 48 bandsman and during the parade you want them to march in the same number of rows. 

So , you calculate the HCF which is 8 and thus you can make 8 rows each for each group.

Write C++ program to find GCD two numbers a and b using  user defined function. i.e. GCD(a,b) using Euclids 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 the values of a and b: "<<endl;

   cin>>a>>b;

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

   return 0;

}

Output:

Enter the values of a and b: 

10

20

GCD of 10 and 20 is 10