Let’s understand the various methods to write a Python program to calculate LCM of two numbers.
What is LCM?
LCM means Lowest Common Multiple. The LCM of two numbers is the smallest number which is a common multiple of both the numbers. The LCM is atleast equal to the larger of the two numbers.
As an example, the LCM of 12 and 16 is 48, because 48 is the lowest number which is a common multiple of both 12 and 16.
The LCM of 2 numbers can be calculated using different methods as given below.
- Listing Multiples method
- Division method
- Prime Factorisation method
Calculating LCM using Listing Multiples method
To find the LCM of two numbers using listing multiples method, generate the multiples of the largest number and find the smallest values which is a common multiple of both the given numbers.
Python Code (to calculate LCM of 2 numbers)
#code to calculate LCM of 2 numbers
def lcm(a, b):
if a>b:
step = a
else:
step = b
lcm = step
while True:
if lcm%a==0 and lcm%b==0:
break
lcm = lcm + step
return lcm
a = 16
b = 12
print("The LCM is ", lcm(a,b))
Calculating LCM using Division method
To find the LCM of two numbers, by using the division method, start the process by dividing the numbers by 2. Continue dividing until both numbers become indivisible by 2. Continue the division process with the next number 3 and so on. Finally, multiply all the factors and the resulting number is the LCM of the given two numbers.
Python Code (to calculate LCM of 2 numbers)
#code to calculate LCM of 2 numbers
def lcm(a, b):
lcm = 1
i = 2
while a>1 or b>1:
if a%i==0 and b%i==0:
a=a//i
b=b//i
lcm = lcm*i
elif a%i ==0:
a=a//i
lcm = lcm*i
elif b%i==0:
b=b//i
lcm=lcm*i
else:
i=i+1
return lcm
a = 18
b = 27
print("The LCM is ", lcm(a,b))
Calculating LCM using Prime Factorisation method
To find the LCM of two numbers, by using the prime factorisation method, generate the prime factors of both the given numbers. Then pair the factors and generate the list of factors. The product is the LCM. Let’s see how to calculate LCM of 18 and 27
Prime Factors of 18 = 2 x 3 x3
Prime Factors of 27 = 3 x 3 x 3
The LCM is 2 x 3 x 3 x 3 = 54
Python Code (to calculate LCM of 2 numbers)
#function to generate prime factors of a given number
def primeFactors(n):
factors=[]
i=2 #start with 2, the smallest prime number
while n>1:
if n%i==0:
factors.append(i)
n=n//i
else:
i=i+1
return factors
#function to calculate LCM using prime factorisation method
def lcm(a, b):
factors_a = primeFactors(a)
factors_b = primeFactors(b)
len_a = len(factors_a)
len_b = len(factors_b)
i = j = 0
lcm = 1
while i<len_a and j<len_b:
if factors_a[i] < factors_b[j]:
lcm = lcm*factors_a[i]
i=i+1
elif factors_b[j] < factors_a[i]:
lcm = lcm*factors_b[j]
j=j+1
else:
lcm = lcm*factors_a[i]
i=i+1
j=j+1
while i<len_a:
lcm = lcm*factors_a[i]
i=i+1
while j<len_b:
lcm = lcm*factors_b[j]
j=j+1
return lcm
a = 18
b = 27
print("The LCM is ", lcm(a,b))