Let’s understand the various methods to write a Python program to calculate HCF of two numbers.
What is HCF?
HCF means Highest Common Factor. The HCF of two numbers is the largest number which can exactly divide both the numbers. The HCF is at most equal to the smaller of the two numbers.
As an example, the HCF of 12 and 16 is 4, because 4 is the highest number which is a factor of both 12 and 16.
The HCF of 2 numbers can be calculated using different methods as given below.
- Listing Factors method
- Division method
- Prime Factorisation method
Calculating HCF using Listing Factors method
To find the HCF of two numbers, generate the factors of the smallest number and find the largest value which is a factor of both the given numbers.
Python Code (to calculate HCF of 2 numbers)
#code to calculate HCF of 2 numbers
def hcf(a, b):
if a<b:
h = a
else:
h = b
while True:
if a%h==0 and b%h==0:
break
h = h - 1
return h
a = 10
b = 15
print("The HCF is ", hcf(a,b))
Calculating HCF using Division method
To find the HCF of two numbers, by using the division method, start the process by dividing both the numbers by 2. If both numbers are divisible by 2, then continue the division with 2. If any one number is not divisible by 2, then continue the division with the next number 3 and so on. Finally, multiply all the factors and the resulting number is the HCF of the given two numbers.
Python Code (to calculate HCF of 2 numbers)
#code to calculate HCF of 2 numbers
def hcf(a, b):
h = 1
i = 2
while i<=a and i<=b:
if a%i==0 and b%i==0:
a = a//i
b = b//i
h = h*i
else:
i = i+1
return h
a = 10
b = 15
print("The HCF is ", hcf(a,b))
Calculating HCF using Prime Factorisation method
To find the HCF of two numbers, by using the prime factorisation method, generate the prime factors of both the given numbers. Then pair the factors and generate the list of common factors. The product is the HCF. Let’s see how to calculate HCF of 18 and 27
Prime Factors of 18 = 2 x 3 x 3
Prime Factors of 27 = 3 x 3 x 3
There are 2 pairs of common factors, hence the HCF is 3×3 = 9
Python Code (to calculate HCF of 2 numbers)
#function to generate prime factors of a given number
def primeFactors(n):
factors=[]
i=2 #start with 2, the smallest prime number
while n>1:
if n%i==0:
factors.append(i)
n=n//i
else:
i=i+1
return factors
#function to calculate HCF using prime factorisation method
def hcf(a, b):
factors_a = primeFactors(a)
factors_b = primeFactors(b)
len_a = len(factors_a)
len_b = len(factors_b)
i = j = 0
h = 1
while i<len_a and j<len_b:
if factors_a[i] < factors_b[j]:
i=i+1
elif factors_b[j] < factors_a[i]:
j=j+1
else:
h = h*factors_a[i]
i=i+1
j=j+1
return h
a = 18
b = 27
print("The HCF is ", hcf(a,b))