Python Highest Common Factor (HCF / GCD)
Calculate the Highest Common Factor (HCF) or Greatest Common Divisor (GCD) of two numbers using the Euclidean algorithm.
How it Works
The Highest Common Factor (HCF), also known as the Greatest Common Divisor (GCD), is the largest positive integer that divides two or more integers without leaving a remainder.
The Euclidean algorithm is an extremely efficient method for computing HCF. It states that the GCD of two numbers also divides their difference.
In Python, we implement this iteratively using a while loop where we continuously replace the larger number with the remainder of their division.
Source Code
Euclidean loop implementation to find HCF/GCD of two numbers.
def find_gcd(a, b):
# Euclidean Algorithm
while b != 0:
a, b = b, a % b
return a
print("GCD of 36 and 60 is:", find_gcd(36, 60))
print("GCD of 17 and 5 is: ", find_gcd(17, 5))GCD of 36 and 60 is: 12
GCD of 17 and 5 is: 1Real-world Applications
- Fraction simplification and math engines
- Cryptography algorithms (like RSA private keys generation)
- Designing periodic event schedules
Frequently Asked Questions
Does Python have a built-in GCD function?
Yes! Python's standard library contains `math.gcd(a, b)` which uses a compiled C implementation under the hood.