Write a Python Program to Find HCF (GCD)

The Highest Common Factor (HCF), also known as the Greatest Common Divisor (GCD), of two numbers is the largest number that divides both numbers completely.

For example, the HCF of 12 and 18 is 6, because 6 is the largest number that can divide both 12 and 18 without leaving a remainder.

In this tutorial, we will write a Python program to find the HCF of two numbers using different methods.

Using a Loop

# Taking user input
num1 = int(input("Enter first number: "))
num2 = int(input("Enter second number: "))

# Finding the smaller number
min_num = min(num1, num2)

# Loop to find HCF
for i in range(min_num, 0, -1):
    if num1 % i == 0 and num2 % i == 0:
        hcf = i
        break

# Printing the result
print("HCF of", num1, "and", num2, "is:", hcf)

Output

Enter first number: 12
Enter second number: 18
HCF of 12 and 18 is: 6

Using Euclidean Algorithm

The Euclidean algorithm is a faster way to compute the HCF using this formula:

Keep repeating this until b becomes 0. The final value of a is the HCF.

def find_hcf(a, b):
    while b:
        a, b = b, a % b
    return a

# Taking user input
num1 = int(input("Enter first number: "))
num2 = int(input("Enter second number: "))

# Calling function
hcf = find_hcf(num1, num2)

# Printing the result
print("HCF of", num1, "and", num2, "is:", hcf)

Output

Enter first number: 48
Enter second number: 18
HCF of 48 and 18 is: 6

Using Python’s Built-in Function

Python provides a built-in function math.gcd() to find HCF quickly.

import math

# Taking user input
num1 = int(input("Enter first number: "))
num2 = int(input("Enter second number: "))

# Using math.gcd() function
hcf = math.gcd(num1, num2)

# Printing the result
print("HCF of", num1, "and", num2, "is:", hcf)

Output

Enter first number: 56
Enter second number: 98
HCF of 56 and 98 is: 14