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.