Program to Find GCD of Two Numbers in C++

Last Updated on May 5, 2023 by Prepbytes

The highest common number that divides two integers without leaving a remainder is known as the GCD (Greatest Common Divisor). Highest Common Factor, or HCF, is another name for GCD. Finding a GCD of two integers can assist you in building the fundamental coding and logical abilities that will advance your profession. GCD of two numbers is used to tackle many challenging problems. The fundamentals for tackling code issues are GCD of two numbers. Returning to our subject, we will examine and resolve the issue of determining the gcd of two numbers.

How to Find GCD of Two Numbers in C++

Find the gcd(M,N) of the two large numbers M and N that are given.
The highest possible number that divides both is GCD(M,N).
It is not difficult to find the GCD of two numbers in c++ programming language. GCD of two numbers can be found by using fundamental math.

Solving Approach on How To Find GCD Of Two Numbers in C++

1. We need to store N in a string since, for the values given, we know it is less than or equal to 100 in size.
2. If we divide any number by N, we know we will always have a residue that is smaller than N.
3. We compute the remainder digit by digit to acquire the remainder by dividing a number stored String by Number. At each digit, the remainder is updated until all strings have been iterated.
4. In every iteration, we take the digit and make it greater than our current remainder by multiplying it by 10 and adding it to the digit, now we take the mod of digit by N and store it as our current remainder. After the whole string is iterated, we will get our remainder.
5. Following the division of M by N and the extraction of the remainder, both numbers fall within the long integer range, allowing us to use the long division method to obtain gcd(M,N), where M is our newly smaller number.
6. Long Division Method: We update Larger number by Smaller number and store the remainder, i.e. (Larger number% Smaller number), regularly until the smaller number entirely divides the larger number. Our gcd is the final smaller number after all steps.

Example:
Two numbers will be presented to us, one of which will be a string and the other a long number. Thus, we discover the remainder of string number and long number. If the given numbers are 143254 and 3, we may test the aforementioned technique by first converting 143254 to a long number, which will be 143254% 3. We take mod=0, which will store our final value, So,

We can now use the long division approach to determine the gcd of both numbers, which is gcd(n,mod), because we know our values in integer form.

Using the long division method, we may find the gcd of two numbers, such as 25 and 135, for example.

Dividend is our gcd(a,b) once our remainder equals 0. Let’s look at the solution for computing the gcd of two numbers in C++.

Code Implementation

#include <bits/stdc++.h>
using namespace std;
long long modBigNumber(string num, long long m) 
{ 
    long long mod = 0; 
    for (int i = 0; i < num.size(); i++) { 
        int digit = num[i] - '0'; 
        mod = mod * 10 + digit; 
        mod = mod % m;         
    }
    return mod; 
}
int main()
{
  long long small;
  long long largeF;
  string large;
  small = 25;
  large = "135";    
  largeF = modBigNumber(large,small);
  if(largeF==0){
    cout<<small<<endl;
  }
  else{
    int temp = small;
    small = largeF;
    largeF = temp;
    while(true){
      if(largeF%small==0){
        cout<<small<<endl;
        break;
      }
      int temp = small;
      small = largeF%small;
      largeF = temp;
    }
  }
}

Output

5

Conclusion
We had discussed how to get a GCD of two numbers in C++ here. Also, we had handled the condition of having a very large number whose GCD is to be calculated. There are a number of ways to implement gcd of two numbers in C++. You have to practice your logical skills to figure out yourself. Finding the gcd of two numbers in C++ programming language will strengthen your logic, and with improved logic, you can get the job of your dreams with ease. Finding the gcd of two numbers in C++ is one of several fundamentals that are necessary for complex tasks.

FAQ for Finding GCD of Two Numbers

Q1. What is the GCD of 24 and 32?
Ans. So, the highest/greatest common factor of 24 and 32 is 8.

Q2. What is GCD or HCF?
Ans. In mathematics, the highest number that divides two integers is known as the GCD (Greatest Common Divisor) or HCF (Highest Common Factor). GCD of 20 and 28 is 4, for instance, whereas GCD of 98 and 56 is 14.

Q3. Which companies asked questions like GCD of two numbers in their interview process?
Ans. In their interviews, Wipro, TCS, Accenture, Cognizant, Capegimini, and Infosys frequently asked candidates to find the GCD of two numbers.

Q4. Are GCD and HCF the same?
Ans. Yes, the greatest common divisor (GCD) and highest common factor (HCF) are the same i.e. the largest numbers that divide them both.