Python Programs to Find HCF and LCM of two numbers

The Highest Common Factor (HCF) of two numbers is the largest number that divides both numbers without leaving a remainder. It is also referred to as the greatest common divisor (GCD). On the other hand, the Least Common Multiple (LCM) is the smallest number, which is a multiple of both numbers.

Python offers multiple ways to find the HCF and LCM, ranging from built-in math modules to custom implementations. This article explores the various ways of calculating HCF and LCM in Python, providing examples and explanations.

1. Using the math Module

In Python, you can use the math module to find the Highest Common Factor (HCF) and the Least Common Multiple (LCM) of two numbers. The math module provides built-in functions math.gcd() for HCF (or GCD).

LCM can be derived using the formula: LCM(a, b) = (|a × b|) / HCF(a, b) (For the division operation, we used floor division. The // operator performs floor division, dividing two numbers and rounding down to the nearest integer by discarding the decimal part, unlike /, which returns a float.)

Note: Python introduced a direct method math.lcm(a, b) in Python 3.9.

Code Example

import math

# Input numbers
a = 24
b = 36

# HCF
hcf = math.gcd(a, b)

# LCM
lcm = (a * b) // hcf

print(f"HCF: {hcf}")
print(f"LCM: {lcm}")Code language: Python (python)

Output

HCF: 12
LCM: 72

2. Using an Iterative Approach

The Euclidean Algorithm is a simple and efficient method for finding the Greatest Common Divisor (GCD), also known as the Highest Common Factor (HCF) of two numbers. The LCM is then derived using the HCF.

Mathematical Representation of Euclidean Algorithm:

For two numbers a and b, where a>b:

1. Compute a mod  b (find remainder).
2. Replace a with b, and b with the remainder.
3. Repeat until b=0.
4. The last non-zero remainder is the HCF.

Let’s take an example to find HCF(48, 18):

1. Divide the larger number (48) by the smaller number (18):
   • 48÷18=24 remainder 12.
   • Replace 48 with 18 and 18 with 12.
2. Repeat the process:
   • 18÷12=1 remainder 6.
   • Replace 18 with 12 and 12 with 6.
3. Continue until the remainder is 0:
   • 12÷6=2 remainder 0.
   • Since the remainder is 0, we stop.
4. The last non-zero remainder (6) is the HCF.
   • HCF(48, 18) = 6.

Code Example

def find_hcf(a, b):
    while b:             # The loop runs until b becomes 0
        a, b = b, a % b  # Update a with b, and b with the remainder
    return a             # When b becomes 0, a is the HCF

# Input numbers
a = 24
b = 36

hcf = find_hcf(a, b)
lcm = (a * b) // hcf    # calculate lcm using hcf

print(f"HCF: {hcf}")
print(f"LCM: {lcm}")

# Output:
# HCF: 12
# LCM: 72Code language: Python (python)

Explanation

• The Euclidean Algorithm works by repeatedly dividing the larger number by the smaller one and taking the remainder. This process continues until the remainder becomes zero. Here The while loop runs until b becomes 0
• HCF Calculation (Using Iteration)
  • We keep replacing a with b and b with a % b (reminder) using a while loop.
  • The loop continues until b becomes 0. At this point a is the HCF.
• The LCM is computed using the same formula as before: LCM(a, b) = (|a × b|) / HCF(a, b)

3. Using Recursion

Recursion is a programming technique where a function calls itself to solve smaller instances of a problem until a base condition is met. This approach employs recursion to implement the Euclidean Algorithm for HCF calculation using Python.

Code Example

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

# Input numbers
a = 24
b = 36

hcf = find_hcf_recursive(a, b)
lcm = (a * b) // hcf   # calculate lcm using hcf

print(f"HCF: {hcf}")
print(f"LCM: {lcm}")

# Output:
# HCF: 12
# LCM: 72Code language: Python (python)

Explanation

• This method uses a recursive implementation of the Euclidean Algorithm. The algorithm reduces the problem size by replacing the larger number with the remainder of its division by the smaller number until the remainder becomes zero.
• For example, if we need the HCF of 36 and 24, the steps would be:
  • Call the function with (36, 24). The remainder is 12, so it calls (24, 12).
  • Call the function with (24, 12). The remainder is 0, so it stops, and the HCF is the last non-zero value, which is 12.
• The LCM is computed using the same formula as before: LCM(a, b) = (|a × b|) / HCF(a, b)

Summary

Each method has its advantages depending on the context. The math module or the Euclidean Algorithm provides the most efficient solutions for most applications.