### What is GCD?

The greatest common divisor is the maximum number which divides two numbers.

For e.g. GCD of 24 and 32:

Divisors of 24: 1,2,3,4,6,8,12.

Divisors of 32: 1,2,4,8,16.

8 is maximum number which divides both of them, Hence GCD of 24 and 32 is 8.

Following is the program to find GCD of 2 numbers in C++

### CODE:

#include<iostream> using namespace std; int main() { int first_number; cout<<"Enter First Number : "; cin>>first_number; int second_number; cout<<"Enter Second Number: "; cin>>second_number; int gcd; for(int i=1;i<=first_number&&i<=second_number;i++){ if(first_number%i==0 && second_number%i == 0 ){ gcd=i; } } cout<<"Greatest Common Divison (GCD):"<<gcd<<endl; return 0; }

This is a very expensive way of computing a gcd. There’s a better algorithm which happens to be one of the oldest algorithms still in use: http://en.wikipedia.org/wiki/Euclidean_algorithm.