How to find GCD of two numbers in C++

Hello, in this tutorial, we will understand how to find GCD of two numbers in C++ in various ways.

Greatest Common Divisor (GCD) or Highest Common Factor (HCF) of two number a and b is the largest number that divides a and b. It is denoted by GCD(a, b).

let’s understand GCD with a simple example

Example : Finding GCD of 24 and 36
          
            24 = 2 × 2 × 2 × 3 × 1     
and,     
            36 = 2 × 2 × 3 × 3 × 1

By compairing each multiplier, we can see that 2 × 2 × 3 are common. 
Therefore GCD(24,36) = 2 × 2 × 3 = 12

This was the simple approach to find GCD of two numbers. It easy to calculate but, a little bit lengthy in the program. Therefore, we will use Euclid’s approach or (Euclidian Algorithm) to find GCD of two number.

Euclid’s method for finding GCD

The Euclidean method is a technique for quickly finding the GCD of two integers.

In Euclid’s method or Algorithm if we need to find GCD(a, b) and if ‘a’ can be represented as a = bq + r where ‘q‘ is quotient and ‘r‘ is remainder. Then, gcd(a, b) = gcd(b, r). same for b.

Example:

Finding gcd(91, 287): 
 
 -> First apply the division algorithm for 287 and 91, therefore 287 = 91*3 + 14. 

 -> from the defination, any common divisor of 287 and 91 must also be a divisor of 14, 
    so, d|(287 − 91*3) = 14. 

 -> now, any common divisor of 91 and 14 must also be a divisor of 287. 
    So, gcd(287,91) = gcd(91,14). 

 -> Now, Continuing the process by dividing 91 by 14. so, 91 = 14 * 6 + 7. 

 -> now, we have gcd(91,14)=gcd(14,7), and divide 14 by 7. 

 -> 14 = 7 · 2 + 0 Because 7 divides 14. 
 -> Therefore, gcd(287,91) = gcd(91,14) = gcd(14,7) = 7.

Algorithm to find GCD of two numbers using iteration

Take input of two numbers in x and y.
find max(x, y) and save to variable ‘a‘.
find min(x, y) and save to variable ‘b‘.
perform iteration for y ≠ 0
(i) save the value of a mod b to ‘r‘
(ii) save the value of b in a and value of r to b.
end the iteration
print value of a.

C++ program to find the GCD of two numbers using iteration

#include<iostream>
using namespace std;

int GCD(int, int);

int main(){
    int y, x;

    cout<<"Enter the two numbers: ";
    cin>>x>>y;

    cout<<"GCD("<< x <<", "<< y <<") = "<< GCD(x, y);
    return 0;
}

int GCD(int x, int y){
    int a, b, r;

    if(x > y){
        a = x;
        b = y;
    }
    else{
        a = y;
        b = x;
    }

    while(b != 0){
        r = a % b;
        a = b;
        b = r;
    }

    return a;
}

Output:

Enter the two numbers: 91
287
GCD(91, 287) = 7

Algorithm to find GCD of two numbers using recursion

Take input of two numbers in x and y.
call the function GCD by passing x and y.
Inside the GCD function call the GDC function by passing y and x%y (i.e. GCD(y, x%y) with the base case y = 0. means, if y is eqal to zero then return x.

C++ program: Find GCD using recursion

#include <iostream> 
using namespace std;    

int GCD(int, int);

int main() 
{ 
    int x , y; 

    cout<<"Enter two number: ";
    cin>>x>>y;
    
    cout<<"GCD("<< x <<", "<< y <<") = "<< GCD(x, y); 

    return 0;
}
   
int GCD(int x, int y) 
{ 
    if (y == 0) 
        return x; 
        
    return GCD(y, x % y);  
      
}