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; } |
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.