C++ program to find the GCD or HCF of two numbers

January 13, 2021

Program to find the GCD or HCF of two numbers

Here we will discuss how to find the GCD or HCF of two numbers entered by the user using C++ programming language.

GCD i.e. Greatest Common Divisible or HCF i.e. Highest Common Factor of two numbers is the largest positive integer that can divide both the numbers

There are many methods to calculate GCD:

Using Prime Factorisation,
Euclid’s Algorithm,
Lehmer’s GCD algorithm, etc

Here we will use Euclid’s Algorithm to find the GCD, which is based on the idea that the GCD doesn’t change when smaller number is subtracted from the greater number. This keeps on going until only the GCD left.

Algorithm:-

Two inputs are taken from the user.
Inputs are stored in two int type variables say first and second.
A recursive program findGCD is called with parameters first and second.
1. First it is checked whether any of the input is 0

if (first == 0)

return second;

if (second==0)

return first;

2. If both input numbers are equal return any of the two numbers

if (first == second)

return second;

3. If first is greater than the second

1. 1. Recursively call findGCD function with parameters ‘first-second’, second.

findGCD(first – second, second);

4. Otherwise recursively call findGCD function with parameters ‘first’, ‘second-first’.

findGCD(first, second – first);

C++ Code:-

    
    //C++ Program
    //GCD of Two Numbers
    #include<iostream>
    using namespace std;
    // Recursive function declaration
    int findGCD(int, int);
    // main program
    int main()
    {
            int first, second;
            cout<<“Enter First Number: “;
            cin>>first;
            cout<<“Enter second Number: “;
            cin>>second;
            cout<<“GCD of “<<first<<” and “<<second<<” is “<<findGCD(first,second);
            return 0;
    }
    //body of the function
    int findGCD(int first, int second)
    {
            // 0 is divisible by every number
            if(first == 0)
            {    
            return second;
            }
            if(second == 0)
            {    
            return first;
            }
            // both numbers are equal
            if(first == second)
            {
            return first;
            }
            // first is greater
            else if(first > second)
            {
            return findGCD(first – second, second);
            }
            return findGCD(first, second – first);
    }

    Output

    Enter First Number: 20
    Enter second Number: 25
    GCD of 20 and 25 is 5

Highest Common Factor(HCF): C | C++ | Java
Lowest Common Multiple (LCM) : C | C++ | Java
Greatest Common Divisor : C | C++ | Java
Binary to Decimal to conversion : C | C++ | Java
Binary to Octal conversion : C | C++ | Java
Decimal to Binary conversion: C | C++ | Java
Decimal to octal Conversion: C | C++ | Java
Octal to Binary conversion : C | C++ | Java
Octal to Decimal conversion : C | C++ | Java
Quadrants in which a given coordinate lies : C | C++ | Java
Permutations in which n people can occupy r seats in a classroom : C | C++ | Java
Maximum number of handshakes: C | C++ | Java
Addition of two fractions: C | C++ | Java
Replace all 0’s with 1 in a given integer : C | C++ | Java
Can a number be expressed as a sum of two prime numbers
: C | C++ | Java