The ones who are crazy enough to think they can change the world are the ones who do.- Steve Jobs
Greatest Common Divisor
What is GCD?
The Greatest Common Divisor(GCD) of two or more integers, when at least one of them is non-zero integer, is the largest positive integer that divides the numbers without any remainder.
The GCD is also well known as HCF(Highest Common Factor) or GCF(Greatest Common Factor).GCD Examples
| Two Numbers | GCD Value |
|---|---|
| 0, 5 | 5 |
| 2, 10 | 2 |
| 9, 12 | 3 |
| 24, 36, 48 | 12 |
Graphical View
When two circles of numbers 9 and 12 are joined each other then GCD of the circles are 3
When three circles of numbers 24, 36 and 48 are joind each other then GCD of the circles are 12
C Program - GCD
Let us write a simple C program to find the GCD of two integers.
#include <stdio.h>
int gcd(int num1, int num2);
int main()
{
int num1, num2;
printf("Enter two positive integers: ");
scanf("%d %d ", &num1, &num2);
printf("G.C.D of %d and %d = %d ", num1, num2, gcd(num1, num2));
return 0;
}
// Function will return gcd of two integer
int gcd(int num1, int num2)
{
if (num2 != 0)
return gcd(num2, num1%num2);
else
return num1;
}
Enter two positive integers : 0 5 G.C.D of 0 and 5 = 5
Note:
Let us focus on int gcd() function. Here the gcd funtion of integer datatype accepts two integers as an input and returns a single integer value. if condition inside gcd function checks whether num2 is not equal to zero. i.e) if(5!=0) for us condition is true and now num1 = num2 and num2 = 0%5. Again the gcd function is called and now if condition fails as num2 = 0 and returns num1 i.e) 5
Related to GCD
Report Us
We may make mistakes(spelling, program bug, typing mistake and etc.), So we have this container to collect mistakes. We highly respect your findings.