GCD Using Simple Method
The idea is to find the minimum of the two numbers and then find the common divisor starting from the minimum number and decrementing it by 1 until a common divisor is found.
Algorithm
- Initialize a variable result with the minimum of a and b.
- Run a loop till the result > 0.
- If both numbers are divisible by the variable result, break the loop.
- Else, decrement the result variable by 1.
- After the loop, the result variable holds the GCD of the two numbers.
- Return the result variable.
C++ Program To Find GCD of Two Numbers Using Simple Method
C++
// C++ program to find GCD of two numbers #include <bits/stdc++.h> using namespace std; // Function to return gcd of a and b int gcd(int a, int b) { // Find Minimum of a and b int result = min(a, b); while (result > 0) { if (a % result == 0 && b % result == 0) { break; } result--; } // Return gcd of a and b return result; } // Driver code int main() { int a = 98, b = 56; cout << "GCD of " << a << " and " << b << " is " << gcd(a, b); return 0; } // This code is contributed by Suruchi Kumari |
Output
GCD of 98 and 56 is 14
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.