GCD of Two Numbers in C
GCD stands for Greatest Common Divisor and is also known as HCF (Highest Common Factor). The GCD of two numbers is the largest positive integer that completely divides both numbers without leaving a remainder.
In this article, we will learn to calculate the GCD of two numbers in the C programming language.
Using Simple Method
To find the GCD of two numbers we will first find the minimum of the two numbers and then find the highest common factor of that minimum which is also the factor of the other number.
Algorithm
- Declare a variable result and initialize it with the minimum of a and b.
- Run a while loop till the result > 0.
- Check if both a and b are divisible by result by using the modulo operator (%), and break the loop.
- Otherwise, decrement result by 1 in each iteration until a common divisor is found or the result becomes 0.
- After the while loop, the result variable will hold the gcd of two numbers. Return the value of the result.
C Program to Find GCD or HCF of Two Numbers
C
// C program to find GCD of two numbers #include <math.h> #include <stdio.h> // Function to return gcd of a and b int gcd( int a, int b) { // Find Minimum of a and b int result = ((a < b) ? a : b); while (result > 0) { // Check if both a and b are divisible by result if (a % result == 0 && b % result == 0) { break ; } result--; } // return gcd of a nd b return result; } // Driver program to test above function int main() { int a = 98, b = 56; printf ( "GCD of %d and %d is %d " , a, b, gcd(a, b)); return 0; } // This code is contributed by Suruchi Kumari |
GCD of 98 and 56 is 14
Complexity Analysis
- Time Complexity: O(min(a,b))
- Auxiliary Space: O(1) or constant
Using Euclidean Algorithm
An efficient solution is to use the Euclidean algorithm which is the main algorithm used for this purpose. The idea is that the GCD of two numbers doesn’t change if a smaller number is subtracted from the bigger number.
Algorithm
- Create a function gcd that takes two integers to find their gcd.
- If a is 0, return b.
- If b is 0, return a.
- If a and b are equal, it means they both are the GCD of themselves, return a or b.
- If a > b, recursively call the gcd function for (a – b) and b. Here we replaced a with the difference between a and b.
- Else, recursively call the gcd function for a and (b – a). Here we replaced b with the difference between b and a.
C Program to Find GCD of Two Numbers Using Euclidean Algorithm
C
// C program to find GCD of two numbers #include <stdio.h> // 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 program to test above function int main() { int a = 98, b = 56; printf ( "GCD of %d and %d is %d " , a, b, 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.
Please refer to the complete article Program to Find GCD or HCF of Two Numbers for more methods to find the GCD of two numbers.
Contact Us