Program to Find the Highest Common Factor (HCF) in Python

Highest Common Factor (HCF)

The Highest Common Factor (HCF) of two numbers is the largest number that divides both of them without leaving a remainder. For example, the HCF of 36 and 60 is 12.

We will explore three different methods to find the HCF of two numbers using Python programming.

Method 1: Using Euclidean Algorithm

We use the Euclidean algorithm, which repeatedly replaces the larger number with its remainder when divided by the smaller number, until the remainder becomes zero.

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

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

print(f"HCF of {num1} and {num2} is {find_hcf(num1, num2)}")
            

Output:

Enter first number: 36
Enter second number: 60
HCF of 36 and 60 is 12

Method 2: Using Prime Factorization

In this method, we find all prime factors of both numbers and take the product of the common ones.

def find_hcf_prime_factorization(a, b):
    def min_val(x, y):
        return x if x < y else y
    
    hcf = 1
    for i in range(2, min_val(a, b) + 1):
        while a % i == 0 and b % i == 0:
            hcf *= i
            a //= i
            b //= i
    return hcf

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

print(f"HCF of {num1} and {num2} is {find_hcf_prime_factorization(num1, num2)}")
            

Output:

Enter first number: 36
Enter second number: 60
HCF of 36 and 60 is 12

Method 3: Using Recursion

We can also find HCF using recursion, following the Euclidean algorithm.

def find_hcf_recursive(a, b):
    if b == 0:
        return a
    return find_hcf_recursive(b, a % b)

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

print(f"HCF of {num1} and {num2} is {find_hcf_recursive(num1, num2)}")
            

Output:

Enter first number: 36
Enter second number: 60
HCF of 36 and 60 is 12