Program to Find the Least Common Multiple (LCM) in Python

Least Common Multiple (LCM)

The Least Common Multiple (LCM) of two numbers is the smallest positive integer that is divisible by both numbers. For example, the LCM of 12 and 18 is 36.

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

Method 1: Using HCF

The LCM of two numbers can be calculated using the formula:

LCM(a, b) = (a * b) / HCF(a, b)

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

def find_lcm(a, b):
    return (a * b) // find_hcf(a, b)

num1 = int(input("Enter first number: "))
num2 = int(input("Enter second number: "))
print(f"LCM of {num1} and {num2} is {find_lcm(num1, num2)}")
            

Output:

Enter first number: 12
Enter second number: 18
LCM of 12 and 18 is 36

Method 2: Using Iteration

We start from the maximum of the two numbers and keep increasing until we find a number that is divisible by both.

def find_lcm_iterative(a, b):
    max_num = max(a, b)
    while True:
        if max_num % a == 0 and max_num % b == 0:
            return max_num
        max_num += 1

num1 = int(input("Enter first number: "))
num2 = int(input("Enter second number: "))
print(f"LCM of {num1} and {num2} is {find_lcm_iterative(num1, num2)}")
            

Output:

Enter first number: 12
Enter second number: 18
LCM of 12 and 18 is 36

Method 3: Using Recursion

We use recursion to find the LCM by incrementing multiples of the larger number until we find a common multiple.

def find_lcm_recursive(a, b, multiple):
    if multiple % a == 0 and multiple % b == 0:
        return multiple
    return find_lcm_recursive(a, b, multiple + 1)

def find_lcm(a, b):
    return find_lcm_recursive(a, b, max(a, b))

num1 = int(input("Enter first number: "))
num2 = int(input("Enter second number: "))
print(f"LCM of {num1} and {num2} is {find_lcm(num1, num2)}")
            

Output:

Enter first number: 12
Enter second number: 18
LCM of 12 and 18 is 36