➤ GCD ( Greatest Common Divisor )
/* The greatest common divisor (GCD) of two or more numbers is the greatest
common factor number that divides them, exactly.
It is also called the highest common factor (HCF).
For example, the greatest common factor of 15 and 10 is 5,
since both the numbers can be divided by 5. */
The GCD, which stands for Greatest Common Divisor,
is the largest positive integer that divides two or more numbers
without leaving a remainder. Finding the GCD of two or more numbers
is a common mathematical operation and has various applications,
especially in mathematics and computer science.
To find the GCD of two numbers, you can use various algorithms
like Euclid's algorithm, which is one of the most efficient methods.
Here's how you can find the GCD of two numbers, let's say "a" and "b":
1. Euclid's Algorithm (recursive):
```
function gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
```
2. Euclid's Algorithm (iterative):
```
function gcd(a, b):
while b != 0:
temp = b
b = a % b
a = temp
return a
```
Example usage:
Let's say we want to find the GCD of two numbers, 24 and 36.
Using Euclid's Algorithm (recursive):
```
gcd(24, 36) = gcd(36, 24) = gcd(24, 12) = gcd(12, 0) = 12
```
Using Euclid's Algorithm (iterative):
```
gcd(24, 36) = gcd(36, 24) = gcd(24, 12) = gcd(12, 0) = 12
```
Both methods yield the same result, which is 12. Therefore,
the Greatest Common Divisor of 24 and 36 is 12.
➤ Program To Calculate GCD Number Between Two Number's using C Language .
#include <stdio.h>
// Function to find the GCD of two numbers using Euclid's algorithm (iterative method)
int gcd(int a, int b) {
int temp;
while (b != 0) {
temp = b;
b = a % b;
a = temp;
}
return a;
}
int main() {
int num1, num2;
printf("Enter two numbers: ");
scanf("%d %d", &num1, &num2);
// Calculate the GCD using the gcd function
int result = gcd(num1, num2);
printf("The GCD of %d and %d is: %d\n", num1, num2, result);
return 0;
}
➤ OUTPUT :
Enter two numbers: 24 86
The GCD of 24 and 86 is: 2
➤ Program To Calculate GCD Number Between Two Number's using Python Language .
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
def main():
num1 = int(input("Enter the first number: "))
num2 = int(input("Enter the second number: "))
result = gcd(num1, num2)
print("The GCD of {} and {} is: {}".format(num1, num2, result))
if __name__ == "__main__":
main()
➤ OUTPUT :
Enter the first number: 56
Enter the second number: 46
The GCD of 56 and 46 is: 2