Finding the GCD of Two Numbers in Python
The Greatest Common Divisor (GCD) of two integers is the largest positive integer that divides both numbers without leaving a remainder. There are several methods to compute the GCD, but one of the most efficient is using the Euclidean algorithm.
The Euclidean algorithm is based on the principle that the GCD of two numbers also divides their difference. The algorithm can be implemented recursively or iteratively. Below is a Python function that implements the Euclidean method to calculate the GCD of two numbers.
Python Function Implementation
def gcd(a, b):
"""
Compute the GCD of two numbers using the Euclidean algorithm.
Parameters:
a (int): First number.
b (int): Second number.
Returns:
int: The GCD of a and b.
"""
while b:
a, b = b, a % b
return abs(a)
How It Works
1. Parameters: The function gcd accepts two integers a and b.
2. Loop: While the second number b is not zero:
- The values of a and b are updated such that a becomes b, and b becomes the remainder of a divided by b.
3. Return Value: The final value of a represents the GCD of the original two numbers. The abs function ensures the result is non-negative.
Example Usage
To use the function, simply call it with two integers:
print(gcd(48, 18)) # Output: 6
print(gcd(54, 24)) # Output: 6
print(gcd(101, 10)) # Output: 1
This function efficiently computes the GCD for any two integers, making it a useful tool in various mathematical and algorithmic applications.