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.