Python Program for LCM Of Two Numbers

LCM of two numbers in Python

 

Here, in this section we will discuss the LCM of two numbers in python.
In this Python Program find the LCM of Two Numbers which numbers are entered by the user. Basically the LCM of two numbers is the smallest number which can divide the both numbers equally. This is also called Least Common Divisor or LCD.

LCM in python

We will learn

  • Method 1: A linear way to calculate LCM
  • Method 2: Modified interval Linear way
  • Method 3: Simple usage of HCF calculation to determine LCM
  • Method 4: Repeated subtraction to calculate HCF and determine LCM
  • Method 5: Recursive repeated subtraction to calculate HCF and determine LCM
  • Method 6: Modulo Recursive repeated subtraction to calculate HCF and determine LCM

Method 1

Algorithm

For a input num1 and num2. This method uses two following observations –

  • LCM of two numbers will at least be equal or greater than max(num1, num2)
  • Largest possibility of LCM will be num1 * num2

When iterating in (i) We can linearly find an (i) that is divisible by both num1 & num2

Method 1 : Python Code

Run
num1 = 12
num2 = 14
for i in range(max(num1, num2), 1 + (num1 * num2)):
    if i % num1 == i % num2 == 0:
        lcm = i
        break
print("LCM of", num1, "and", num2, "is", lcm)

Output

LCM of 12 and 14 is 84

Method 2

Algorithm

For input num1 and num2. This method uses two following observations –

  • Rather than linearly checking for LCM by doing i++. We can do i = i + max
  • Starting with i = max (num1, num2)
  • The next possibility of LCM will be ‘max’ interval apart

Method 2 : Python Code

Run
num1 = 12
num2 = 14
for i in range(max(num1, num2), 1 + (num1 * num2), max(num1, num2)):
    if i % num1 == i % num2 == 0:
        lcm = i
        break

print("LCM of", num1, "and", num2, "is", lcm)

Output

LCM of 12 and 14 is 84

Method 3

Algorithm

  • Initialize HCF = 1
  • Run a loop in the iteration of (i) between [1, min(num1, num2)]
  • Note down the highest number that divides both num1 & num2
  • If i satisfies (num1 % i == 0 && num2 % i == 0) then new value of HCF is i
  • Use lcm formula :- (num1*num2) / hcf
  • Print the output

Method 3 : Python Code

Run
num1 = 12
num2 = 14

# Calculating HCF here
for i in range(1, max(num1, num2)):
    if num1 % i == num2 % i == 0:
        hcf = i

# LCM formula
lcm = (num1*num2)//hcf

print("LCM of", num1, "and", num2, "is", lcm)

Output

LCM of 12 and 14 is 84

Method 4

Algorithm

  • Run a while loop until num1 is not equals to num2
  • If num1>num2 then num1 = num1 – num2
  • Else num2 = num2 – num1
  • After the loop ends both num1 & num2 stores HCF
  • Use LCM formula :- (num1*num2) / hcf
  • Print Output

Method 4 : Python Code

Run
def getHCF(num1, num2):
    while num1!=num2:
        if num1>num2:
            num1-=num2
        else:
            num2-=num1
    return num1


num1 = 12
num2 = 14

# Calculating HCF here
hcf = getHCF(num1, num2)

# LCM formula
lcm = (num1*num2)//hcf

print("LCM of", num1, "and", num2, "is", lcm)

Output

LCM of 12 and 14 is 84

Method 5

Algorithm

  • Checked whether any of the input is 0 then return sum of both numbers
  • If both input are equal return any of the two numbers
  • If num1 is greater than the num2 then Recursively call findHCF(num1 – num2, num2)
  • Else Recursively call findHCF(num1, num2-num1)

Method 5 : Python Code

Run
# Recursive function to return HCF of two number
def getHCF(num1, num2):
    # Everything divides 0
    if num1 == 0 or num2 == 0:
        return num1 + num2

    # base case
    if num1 == num2:
        return num1

    # num1>num2
    if num1 > num2:
        return getHCF(num1 - num2, num2)
    else:
        return getHCF(num1, num2 - num1)


num1 = 12
num2 = 14

# Calculating HCF here
hcf = getHCF(num1, num2)

# LCM formula
lcm = (num1*num2)//hcf

print("LCM of", num1, "and", num2, "is", lcm)

Output

LCM of 12 and 14 is 84

Method 6

Algorithm

This method uses recursion.

In Addition, we are using modulo operation to reduce the number of subtractions required and improve the time complexity

For this method, you need to know how to calculate HCF, check this post here

We use repeated Modulo Recursive subtraction (Euclidean Algorithm) to calculate the HCF.

Method 6 : Python Code

Run
def getHCF(a, b):
    if b == 0:
        return a
    else:
        return getHCF(b, a % b)


num1 = 12
num2 = 14
hcf = getHCF(num1, num2)

# LCM formula
lcm = (num1 * num2) // hcf
print("The hcf is :", lcm)

Output

LCM of 12 and 14 is 84

3 comments on “Python Program for LCM Of Two Numbers”


  • karalesamarth18

    import math as m
    num1 = int(input(‘Enter first number: ‘))
    num2 = int(input(‘Enter second number: ‘))
    HCF = m.gcd(num1,num2)
    LCM = int((num1*num2)/(HCF))
    print(‘LCM of given numbers: ‘, LCM)


  • Aditya

    x=int(input(“enter first number : “))
    y=int(input(“enter second number : “))
    def lcm(a,b):
    if a>b:
    bigger=a
    else:
    bigger=b
    for i in range(bigger,(a*b)+1):
    if i%a==0 and i%b==0:
    lcm_of_num=i
    break
    return lcm_of_num
    print(lcm(x,y))


  • Sonal

    num1=int(input(“Enter the 1st number”))
    num1=int(input(“Enter the 2nd number”))
    l=[]
    for i in range(1,min(num1,num2)):
    if (num1%i==0) and (num2%i==0):
    l.append(i)
    else:
    continue
    hcf=max(l)
    lcm=(num1*num2)//hcf
    print(“{} is the LCM of {} and {}”.format(hcf,num1,num2))