Find the HCF of two numbers in Python

In this tutorial, we will learn to find HCF (Highest Common Factor) of two numbers in Python. The Highest Common Factor (HCF) or Greatest Common Divisor (GCD) is the largest positive number which perfectly divides the given numbers. So, we will learn a method to find HCF or GCD. Also, we will see a Python program that will find the HCF of two numbers given as input by the user.

Method to find the HCF of two numbers

To find the HCF of two numbers given as input by the user, we will follow the steps given below-

Take the number which is smaller between the two and store it in variable ‘small’.
Take a variable, say ‘i’ and initialize it with 1.
Check whether the two numbers are divisible by ‘i’.
If both the numbers are divisible, then store the value of ‘i’ in another variable ‘result’.
Increment the value of ‘i’ by 1.
Continue the above steps until the value of ‘i’ becomes equal to the value in ‘small’.
Finally, the value store in the variable ‘i’ is the result i.e. HCF.

Python program to find the HCF of two numbers

We will see a Python program to find the HCF of two numbers given by the user. Firstly, we will take the two numbers from the user as input. There are two methods to calculate the HCF-

By using math.gcd() inbuilt function
By defining a user-defined function

Using math.gcd() inbuilt function

The math module of Python provides various mathematical functions for performing basic tasks. So, we will use the gcd() function which returns the GCD or HCF. The Python program to find the HCF of two numbers using math.gcd() function is-

import math
number1 = int(input("ENTER FIRST NUMBER : "))
number2 = int(input("ENTER SECOND NUMBER : "))
print("THE HCF OF ",number1," AND ",number2," IS : ",math.gcd(number1,number2))

Using a user-defined function

We can also calculate the HCF using a user-defined function. Here, we define a function ‘calc_hcf’ to calculate the HCF of given numbers. Using a ‘for’ loop, we find the highest common factor of the two numbers. And finally, we display the HCF as output. So, the Python program is given below-

def calc_hcf(n1,n2):
  if n1 > n2:
    small = n2
  else:
    small = n1
  for i in range(1,small + 1):
    if((n1 % i == 0) and (n2 % i == 0)):
      result = i
  return result
number1 = int(input("ENTER FIRST NUMBER : "))
number2 = int(input("ENTER SECOND NUMBER : "))
print("THE HCF OF ",number1," AND ",number2," IS : ",calc_hcf(number1, number2))

Python program output

The output of both the Python programs will be the same. Because the inbuilt function and the user-defined function return the same results. The program displays the HCF or GCD as output to the user. The output is given below-

[email protected]:~/python$ python3 hcf.py
ENTER FIRST NUMBER : 21
ENTER SECOND NUMBER : 9
THE HCF OF  21  AND  9  IS :  3
[email protected]:~/python$

So, the HCF of 21 and 9 is 3.

Also read: Python Program to find LCM of two numbers