C++ Program to Find GCD

C++ gcd function – C++ Program to Find GCD

by

C++ gcd function: In the previous article, we have discussed about C++ Program to Find Factorial. Let us learn how to find GCD in C++ Program.

Methods to find HCF/GCD of two numbers in c++

In this article, we will discuss different methods in c++ for calculating the GCD/HCF of two numbers. The list of methods that we will discuss is given below:-

First of all, let understand what a GCD/HCF is. GCD or HCF of two numbers is the largest number that divides both of them. For example, GCD of 36 and 60 will be equal to 12 because 12 is the largest num, ber that divides both 36 and 60.

Method 1-Using loop and if statement

The idea here is that we will find the common divisor of two numbers starting from 1 and then return the largest divisor. Let write the code for this.

#include <iostream>

using namespace std;

int main()
{
     int num1=36, num2=60, i, gcd;
    for(i=1; i <= num1 && i <= num2; i++)
    {
        if(num1%i==0 && num2%i==0)
            gcd = i;
    }
    cout<<"GCD of two numbers "<<num1<<" and "<<num2<<" is "<<gcd;
   
    return 0;
}

Output

GCD of two numbers 36 and 60 is 12

Method 2- Using Recursion

Here idea is that the GCD of two numbers doesn’t change if a smaller number is subtracted from a bigger number. So we use this idea with recursion and find the gcd of two numbers. Let’s write the code for this.

#include <iostream>

using namespace std;

int gcd_of_number(int num1, int num2)
{
    if (num1 == 0)
       return num2;
    if (num2 == 0)
       return num1;
  
    if (num1 == num2)
        return num1;
  
    
    if (num1 > num2)
        return gcd_of_number(num1-num2, num2);
    return gcd_of_number(num1,num2-num1);
}
int main()
{
     int num1=36, num2=60, i, gcd;
    
    cout<<"GCD of two numbers "<<num1<<" and "<<num2<<" is "<<gcd_of_number(num1,num2);
   
    return 0;
}

Output

GCD of two numbers 36 and 60 is 12

Method 3-Using recursion with the modulo(%) operator

Here the idea is the same as the above method but here we use the modulo operator where we are able to write the same idea in fewer lines. Let’s write the code for this.

#include <iostream>

using namespace std;

int gcd_of_number(int num1, int num2)
{
    if (num2 == 0)
        return num1;
    return gcd_of_number(num2, num1 % num2);
     
}
int main()
{
     int num1=36, num2=60, i, gcd;
    
    cout<<"GCD of two numbers "<<num1<<" and "<<num2<<" is "<<gcd_of_number(num1,num2);
   
    return 0;
}

Output

GCD of two numbers 36 and 60 is 12

Method 4-Using inbuilt function

C++ has the built-in function for calculating GCD. This function returns 0 if both m and n are zero, else returns the gcd of two numbers. Let’s write code for this.

#include <bits/stdc++.h>

using namespace std;

int main()
{
     int num1=36, num2=60, i, gcd;
    
    cout<<"GCD of two numbers "<<num1<<" and "<<num2<<" is "<<__gcd(num1,num2);
   
    return 0;
}

Output

GCD of two numbers 36 and 60 is 12

So these are the methods to find GCD/HCF of two numbers in c++.