In this tutorial, we will learn how to find the Highest Common Factor (HCF) or Greatest Common Divisor (GCD) of two numbers in Python. We will cover the basic concept of HCF/GCD and implement functions to perform the calculation using both the built-in math library and a regular method.
The Highest Common Factor (HCF) or Greatest Common Divisor (GCD) of two or more integers is the largest positive integer that divides each of the integers without leaving a remainder. For example, the HCF/GCD of 8 and 12 is 4.
The syntax to find the HCF or GCD of two numbers in Python can be done in two ways:
import math
def find_hcf_math(a, b):
return math.gcd(a, b)
def find_hcf_regular(a, b):
while b:
a, b = b, a % b
return a
We can use the built-in math library in Python to find the HCF or GCD of two numbers.
For example,
math
module.find_hcf_math
that takes two parameters a
and b
.math.gcd
function to find the HCF or GCD of the two numbers.import math
def find_hcf_math(a, b):
return math.gcd(a, b)
# Find the HCF/GCD of 8 and 12 using the math library
result = find_hcf_math(8, 12)
# Print the result
print('HCF/GCD of 8 and 12 using math library is', result)
HCF/GCD of 8 and 12 using math library is 4
We can use the Euclidean algorithm to find the HCF or GCD of two numbers by iterating through the modulo operation.
For example,
find_hcf_regular
that takes two parameters a
and b
.while
loop to iterate until b
becomes zero.a
to b
and b
to a % b
.a
after the loop ends.def find_hcf_regular(a, b):
while b:
a, b = b, a % b
return a
# Find the HCF/GCD of 8 and 12 using the regular method
result = find_hcf_regular(8, 12)
# Print the result
print('HCF/GCD of 8 and 12 using regular method is', result)
HCF/GCD of 8 and 12 using regular method is 4