GCD of Two Numbers in C++

In this post, we will develop a program to find GCD or HCF of two numbers in C++. We will also develop program using recursion and function.

The Greatest Common Divisor (GCD) of two or more numbers is the greatest number which divides each of them exactly. Greatest Common Measure(GCM) and highest common factor (HCF) are the other terms used to refer to HCF.

Example: HCF of 60 and 75 = 15 because 15 is the highest number which divides both 60 and 75 exactly.

C++ program to find GCD (Greatest common divisior) through subtracting numbers.

#include<iostream>
using namespace std;
int main()
{
  // declare two variables
  int num1, num2;

  // take inputs
  cout << "Enter Two Integers: ";
  cin >> num1 >> num2;

  // find GCD
  while( num1 != num2 )
  {
    if(num1 > num2)
       num1 -= num2 ;
    else
      num2 -= num1 ;
  }

  // display result
  cout << "GCD = "<< num1 << endl;

  return 0;
}

Output:-

Enter Two Integers: 12 15
GCD = 3

The num1 and num2 are two variables which stores value of two integers. Inside while loop, if num1 will be greater than num2 then num1 = num1 – num2 will evaluated otherwise num2 = num2 – num1. This process continuous until num1 and num2 becomes equal.

if(num1 > num2)
num1 -= num2 ;
else
num2 -= num1 ;

These line of code can be replaced by,

( num1 > num2 ) ? (num1 -= num2) : (num2 -= num1);

Another way

#include<iostream>
using namespace std;
int main()
{
  // declare variables
  int num1, num2, gcd;

  // take inputs
  cout << "Enter Two Integers: ";
  cin >> num1 >> num2;

  // swap num1 and num2
  // if num2 is greater than num1
  if(num2 > num1)
  {
     // swap using bitwise XOR operator
     num1^=num2^=num1^=num2; 
  }
  
  for(int i=1; i<=num1; i++ )
  {
    if(num1%i==0  && num2%i==0)
       gcd=i;
  }

  cout << "GCD = " << gcd << endl;
  return 0;
}

C++ Program to Find GCD of Two Numbers Using Function

In this program we can use any of the above technique to find the GCD of two numbers in C++.

#include<iostream>
using namespace std;
int findGCD(int, int);
int main()
{
  // declare variables
  int num1, num2, gcd;

  // take inputs
  cout << "Enter Two Integers: ";
  cin >> num1 >> num2;

  // find GCD
  gcd = findGCD(num1, num2);

  cout << "GCD = " << gcd << endl;
  return 0;
}

// function to find GCD 
int findGCD(int m, int n)
{
    while( m != n )
    ( m > n ) ? (m -= n) : (n -= m);
    
    return m;
}

GCD of Two Numbers in C++ Using LCM

The product of two numbers a and b is equal to the product of GCD(a,b) and LCM(a,b).

a*b = GCD(a,b) * LCM(a,b)

In the below GCD program in java, we first find the LCM of numbers then the using the given formula GCD of numbers will be calculated. The Formula used for this purpose is:-

GCD(a,b) = (a*b) / LCM(a,b)

#include<iostream>
using namespace std;
long findGCD(int, int);
long findLCM(int, int);
int main()
{
  // declare variables
  int num1, num2;
  long gcd;

  // take inputs
  cout << "Enter Two Integers: ";
  cin >> num1 >> num2;

  // find GCD
  gcd = findGCD(num1, num2);

  cout << "GCD = " << gcd << endl;
  return 0;
}

// function to find GCD of 2 numbers
// GCD = ( n1*n2 ) / LCM(n1,n2)
long findGCD(int m, int n)
{
  return (m*n) / findLCM(m, n);
}

// function to find LCM of 2 numbers
long findLCM(int n1, int n2) 
{

   // declare temporary variable to find lcm
   long minMultiple = 0;

   // find smallest and largest number 
   int smallest = (n1 < n2) ? n1 : n2;
   int largest = (n1 > n2) ? n1 : n2; 

   // assign smallest number to minMultiple
   minMultiple = smallest;

   // loop
   while(true) {
      if(minMultiple % largest == 0)
        return minMultiple;
      minMultiple = minMultiple + smallest ;
   }
}

GCD Using Recursion C++

We can also use the recursion technique to find the GCD of two numbers. A technique of defining the method/function that contains a call to itself is called the recursion. The recursive function/method allows us to divide the complex problem into identical single simple cases that can handle easily. This is also a well-known computer programming technique: divide and conquer.

#include<iostream>
using namespace std;
int findGCD(int, int);
int main()
{
  // declare variables
  int num1, num2, gcd;

  // take inputs
  cout << "Enter Two Integers: ";
  cin >> num1 >> num2;

  // find GCD
  gcd = findGCD(num1, num2);

  cout << "GCD = " << gcd << endl;
  return 0;
}

// recursive function to find GCD of 2 numbers
int findGCD(int num1, int num2)
{
  if(num2 == 0) // base case
     return num1; 
  else // general case
     return findGCD(num2, num1%num2);
}

If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or do you find anything incorrect? Let us know in the comments. Thank you!