GCD Using Euclidean Algorithm

The Euclidean algorithm is an efficient method to find the GCD of two numbers. It works on the principle that the GCD of two numbers remains the same if the greater number is replaced by the difference between the two numbers.

Algorithm

Define a function that takes two integers to find their GCD.
If a is equal to 0, then the GCD of a and b is b.
If b is equal to 0, then the GCD of a and b is a.
If a and b are equal, the GCD is a or b.
If a > b, call the gcd function recursively with parameters (a – b, b).
Else, call the gcd function recursively with parameters (a, b-a).

C++ Program to Find GCD of Two Numbers Using Euclidean Algorithm

C++

// C++ program to find GCD 
// of two numbers 
#include <iostream> 
using namespace std; 
  
// Recursive function to return 
// gcd of a and b 
int gcd(int a, int b) 
{ 
    // Everything divides 0 
    if (a == 0) 
        return b; 
    if (b == 0) 
        return a; 
  
    // base case 
    if (a == b) 
        return a; 
  
    // a is greater 
    if (a > b) 
        return gcd(a - b, b); 
    return gcd(a, b - a); 
} 
  
// Driver code 
int main() 
{ 
    int a = 98, b = 56; 
    cout << "GCD of " << a << " and " << b << " is "
         << gcd(a, b); 
    return 0; 
}

Output

GCD of 98 and 56 is 14

Explanation

a = 98 and b = 56
a > b so put a = a - b and b remains the same.
So a = 98 - 56 = 42 and b = 56. 
Now b > a so b = b - a and a is same b= 56-42 = 14 & a= 42. 
42 is 3 times 14
HCF is 14.

Complexity Analysis

Time Complexity: O(min(a,b))
Auxiliary Space: O(min(a,b))

GCD of Two Numbers in C++

GCD (Greatest Common Divisor) or HCF (Highest Common Factor) of two numbers is the largest number that exactly divides both numbers. In this article, we will learn to write a C++ program to find the GCD of two numbers.

Recommended PracticeLCM And GCDTry It!

Tags:

#C++ Basic Programs #C++ #C++ Programs #CPP

1. GCD Using Simple Method

3. GCD Using Inbuilt Function in C++