Program to calculate HCF of two numbers

The Highest Common Factor (HCF), also universally known as the Greatest Common Divisor (GCD), is a core mathematical concept used in simplifying fractions, cryptography, and algorithm optimization. In Python, calculating the HCF can be done through a basic looping method, a highly optimized mathematical algorithm, or by utilizing Python's robust standard library. Let's explore the best ways to implement this.

1. Conceptual Understanding: Defining HCF

The Highest Common Factor (HCF) of two or more non-zero integers is the largest positive integer that divides each of the numbers without leaving a remainder.

Conceptual Visual Example: Divisors of 12 and 18

Let's look at the factors (divisors) for 12 and 18:

• Factors of 12: 1, 2, 3, 4, 6, 12
• Factors of 18: 1, 2, 3, 6, 9, 18

The common factors are 1, 2, 3, and 6. The highest of these is 6. Therefore, HCF(12, 18) = 6.

2. Implementation in Python: Method 1 (Using Loops)

This is the intuitive, brute-force approach. We know the HCF cannot be larger than the smaller of the two numbers. So, we find the smaller number and use a for loop to iterate from 1 up to that smaller number, checking if both numbers are completely divisible by the current loop variable.

# Method 1: finding HCF using a loop
def compute_hcf(x, y):
    # Determine the smaller number
    if x > y:
        smaller = y
    else:
        smaller = x
        
    hcf = 1 # Default HCF
    
    # Iterate from 1 to the smaller number
    for i in range(1, smaller + 1):
        if (x % i == 0) and (y % i == 0):
            hcf = i 
            
    return hcf

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

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

3. Mathematical Optimization: Method 2 (The Euclidean Algorithm)

The Euclidean Algorithm is a wildly efficient method for finding the HCF, dating back to 300 BC. The algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. In modern programming, we use the modulo operator (%) to find the remainder instead of subtracting repeatedly, making it even faster.

# Method 2: efficient HCF calculation using Euclidean Algorithm
def compute_hcf_euclidean(x, y):
    # Loop continues until y becomes 0
    while(y):
        # Swap x and y. Make y the remainder of x divided by y
        x, y = y, x % y
        
    # When y is 0, x is the HCF
    return x

n1 = 54
n2 = 24
print(f"The HCF of {n1} and {n2} is {compute_hcf_euclidean(n1, n2)}")

4. The Pythonic Way: Method 3 (Using math.gcd)

As with many common mathematical operations, Python provides a built-in, highly optimized function written in C under the hood. Unless you are asked to write the algorithm from scratch for an interview or assignment, you should always use the math module in production code.

# Method 3: The standard library approach
import math

val1 = 36
val2 = 60

# Calculating GCD (HCF) directly
result = math.gcd(val1, val2)

print(f"The HCF of {val1} and {val2} is {result}")