Python Program: Finding Highest Common Factor (HCF)

In this blog post, we will explore the concept of the Highest Common Factor (HCF) and provide a detailed Python program to find the HCF of two numbers. The article will cover the algorithm behind the HCF calculation, present the Python code for implementation, and include examples with corresponding outputs.

Understanding the Algorithm

The HCF, also known as the Greatest Common Divisor (GCD), is the largest positive integer that divides two or more numbers without leaving a remainder. The algorithm for finding the HCF of two numbers involves the following steps:

Euclidean Algorithm:

1. Input Numbers: Receive the two numbers for which the HCF needs to be calculated.
2. Find Remainder: Use the Euclidean Algorithm to find the remainder when the larger number is divided by the smaller number.
3. Swap and Repeat: Swap the numbers (put the smaller number first and the remainder second), and repeat the process until the remainder becomes zero.
4. Last Non-Zero Remainder: The last non-zero remainder obtained in the process is the HCF of the two numbers.

Python Program for Finding HCF

Let’s implement the Euclidean Algorithm in a Python program:

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

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

# Calculate and display HCF
hcf_result = calculate_hcf(num1, num2)
print(f"The HCF of {num1} and {num2} is: {hcf_result}")

Output Example

Example: Finding HCF of 48 and 18

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

Explanation

The Python program defines a function calculate_hcf that implements the Euclidean Algorithm to find the HCF of two numbers. The while loop iteratively swaps and calculates remainders until the remainder becomes zero. The last non-zero remainder is the HCF. The input function is used to take user input, and the result is displayed.

Conclusion

This Python program offers an efficient and straightforward method for finding the Highest Common Factor (HCF) of two numbers using the Euclidean Algorithm. You can use this program as a standalone utility or incorporate it into larger Python projects. Feel free to experiment with different input values and explore variations of the algorithm. If you have any questions or would like to delve into more Python programming topics, please don’t hesitate to ask!