Progress

Python program to find LCM of two numbers

Python program to find LCM of two numbers

Problem Statement: Write a Python program to find least common multiple or LCM of two numbers.

Description: LCM of two numbers is the smallest number which can be completely divided by both the numbers.

Example:

Input: 20 25
Output: LCM of 20 and 25 is 100.
Explanation: 20*5=100 and 25*4=100 and 100 is lowest number which can be divided by both numbers.

Input: 5 7
Output: LCM of 5 and 7 is 35.
Explanation: 5*7=35 and 7*5=35 and 35 is lowest number which can be divided by both numbers.

Python Program: Find LCM of two Numbers

lcm.py
Copy
def find_lcm(num1, num2):
    smallerNum = min(num1, num2)
    greaterNum = max(num1, num2)
    for i in range(1, greaterNum+1):
        if((smallerNum*i)%greaterNum==0):
            return smallerNum*i
    return num1*num2


num1 = 4
num2 = 22

#num1,num2 = map(int, input("Enter two numbers separated by space:\n").split(" "))

print("LCM of {0} and {1} is {2}".format(num1, num2, find_lcm(num1, num2)))
Output
LCM of 4 and 22 is 44

Before diving into the logic of the code you should know that worst-case LCM of two numbers (a, b) is a*b.

The first step is to find the smaller and larger number among the two.

We iterate from 1 to the greater number (inclusive). We choose the greater number because the worst-case LCM is smaller number*greater number.

Then we multiply each number to the smaller number and check if it is divisible by the greater number.

Once we find the number which is divisible by both numbers then it is the LCM.

Python Program: Find LCM using GCD

This program is based on the fact that the product of two numbers is equal to the LCM and HCF of those numbers.

Number1*Number2 = LCM(Number1, Number2)*HCF(Number1, Number2)

LCM(Number1, Number2) = (Number1*Number2)/ HCF(Number1, Number2)

Here is the Python implementation of the above formula to find LCM of two numbers using GCD or HCF.

Copy
def find_hcf(num1, num2):
    smallerNum = min(num1, num2)
    gcd = 1
    for i in range(1, smallerNum+1):
        if(num1%i==0 and num2%i==0):
            gcd = i
    return gcd

num1 = 4
num2 = 22

#num1,num2 = map(int, input("Enter two numbers separated by space:\n").split(" "))

lcm = (num1*num2)/find_hcf(num1, num2)

print("LCM of {0} and {1} is {2}".format(num1, num2, lcm))
Output
LCM of 4 and 22 is 44.0

You can read more about the logic to find HCF or GCD in Python.

The LCM is calculated using the formula described above and we print the results.

Share the Post ;)

Related Posts