Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is LCM?
2.1.
Features of LCM
3.
Python Program to Compute LCM
3.1.
Python
3.2.
Find the LCM of Two Numbers Using Loop
3.3.
Python
3.4.
Find LCM of Two Numbers Using Prime Factorization
3.5.
Python
3.6.
Find LCM of Two Numbers Using the GCD
3.7.
Python
3.8.
Find LCM of Two Numbers Using numPy
3.9.
Python
4.
Frequently Asked Questions
4.1.
How to find LCM of 3 numbers in Python?
4.2.
How to find LCM in programming?
4.3.
Can LCM be negative?
4.4.
Can we find LCM of more than two numbers?
5.
Conclusion
Last Updated: May 16, 2024
Easy

Python Program to Find LCM

Author Surbhi Sharma
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

In mathematics, the lowest number that is a multiple of two or more specified numbers is known as the least common multiple, or LCM. It is a key idea in number theory and is frequently applied in many mathematical applications. Finding the Least Common Multiple (LCM) of two or more numbers is a common mathematical operation used in various fields, including mathematics, computer science, and engineering. In this blog, we will explore how to write a Python program to find the LCM of two integers using different methods and techniques.

Introduction

What is LCM?

The smallest positive integer divided by two or more integers is the least common multiple (LCM). For instance, the lowest number that is a multiple of 4 and 6 is 12, making it the LCM of 4 and 6.

Finding each integer's prime factorization and multiplying the greatest power of each prime factor together yields the LCM. Refer to the image provided for better understanding. 

LCM of 12 and 18

Features of LCM

  1. The lowest multiple is the least common multiple (LCM) between two or more numbers.
     
  2. The value of LCM is always positive.
     
  3. Finding each number's prime factorization and multiplying the greatest power of each prime factor together yields the LCM formula.
     
  4. The relationship between LCM and GCD is shown by the formula LCM(a,b) x GCD(a,b) = a x b.
     
  5. Since LCM is not commutative nor associative, the outcome can be influenced by the arrangement of the numbers.
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Python Program to Compute LCM

To compute the Least Common Multiple (LCM) of two integers in Python, we can use either a mathematical approach or an algorithmic approach such as the Euclidean algorithm. Here's an example of how to compute LCM using the mathematical approach:

  • Python

Python

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

def lcm(a, b):
return (a * b) // gcd(a, b)

num1 = 12
num2 = 15

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

 

Output:

LCM of 12 and 15 is: 60

In this example, we define two functions: gcd() to calculate the Greatest Common Divisor (GCD) using the Euclidean algorithm, and lcm() to compute the LCM using the formula: LCM(a, b) = (a * b) / GCD(a, b). We then provide two integers num1 and num2, compute their LCM using the lcm() function, and print the result.

Find the LCM of Two Numbers Using Loop

Loops are one of the easiest ways to determine the LCM of two or more numbers. 

This below written python code example shows how to use loops to get the LCM

  • Python

Python

def calculate_lcm(x, y):
if x > y:
greater = x
else:
greater = y

while(True):
if((greater % x == 0) and (greater % y == 0)):
lcm = greater
break
greater += 1

return lcm

num1 = 12
num2 = 18

print("The LCM of", num1, "and", num2, "is", calculate_lcm(num1, num2))


Output

The LCM of 12 and 18 is 36


Time Complexity 

The above code has an O(N) time complexity, where N is the largest value that can be found between x and y. This is so because N, the largest possible value between x and y, is the greatest number of iterations that the while loop may have before finding the least common multiple (LCM) of x and y.

Space Complexity

The code's space complexity is O(1), therefore, regardless of the size of the input, it uses the same amount of memory. This is so because the code, regardless of the quantity of the input, only employs a constant number of variables.

Explanation

First find the greater number among the 2 input numbers provided. After that, run an infinite loop until the bigger number completely divides both the numbers. We will divide the greater number by a and b. If both the numbers can divide the greater number completely, we have found our lcm. Otherwise, we will increment the greater number by 1 and perform the same above process until the greater number completely divides the numbers a and b.

Find LCM of Two Numbers Using Prime Factorization

One approach to finding the Least Common Multiple (LCM) of two numbers is by using prime factorization. To compute the LCM using prime factorization, we find the prime factors of each number and then multiply together the highest power of each prime factor present in both numbers. Here's how to do it in Python:

  • Python

Python

def prime_factors(n):
factors = []
divisor = 2
while n > 1:
while n % divisor == 0:
factors.append(divisor)
n //= divisor
divisor += 1
return factors

def lcm_prime_factorization(a, b):
factors_a = prime_factors(a)
factors_b = prime_factors(b)
lcm = 1
for factor in set(factors_a + factors_b):
lcm *= factor ** max(factors_a.count(factor), factors_b.count(factor))
return lcm

num1 = 12
num2 = 15

lcm_result = lcm_prime_factorization(num1, num2)
print("LCM of", num1, "and", num2, "is:", lcm_result)

 

Output:

LCM of 12 and 15 is: 60

In this example, we first define a function prime_factors() to find the prime factors of a given number. Then, we define the lcm_prime_factorization() function to compute the LCM using prime factorization. We find the prime factors of both numbers num1 and num2, and then calculate the LCM by multiplying together the highest power of each prime factor present in both numbers. Finally, we print the LCM result.

Find LCM of Two Numbers Using the GCD

Using the GCD (Greatest Common Divisor) or HCF (Highest Common Factor) is another method for calculating the LCM of two or more numbers. 

GCD of two numbers is the largest positive integer that divides both the numbers.

The relationship between LCM and GCD is shown by the formula LCM(a,b) x GCD(a,b) = a x b.

To use the GCD function, we first import the math module in the code above. Then, by multiplying and dividing the two input numbers by their GCDs, we arrive at the LCM.

Syntax

  • Python

Python

import math
def lcm_using_gcd(num1, num2):
   lcm = (num1*num2)//math.gcd(num1,num2)
   return lcm
   
num1 = 12
num2 = 18
print("The LCM of", num1, "and", num2, "is", lcm_using_gcd(num1, num2))


Output

The LCM of 12 and 18 is 36


Built-in math.gcd has Time Complexity of O(log(min(num1, num2))) and Space Complexity of O(1).

Find LCM of Two Numbers Using numPy

NumPy is a well-known Python library for doing numerical calculations. The LCM of two or more numbers may be determined using NumPy. 

The Python code to find the LCM using NumPy is given below

  • Python

Python

import numpy as np
def lcm_using_numpy(num1, num2):
   lcm = np.lcm(num1, num2)
   return lcm

num1 = 12
num2 = 18
print("The LCM of", num1, "and", num2, "is", lcm_using_numpy(num1, num2))


Output

The LCM of 12 and 18 is 36


Time Complexity

The code provided has an O(1) time complexity. This is because, regardless of the quantity of the input, the code only does a certain number of operations. The code specifically invokes the built-in numPy function np.lcm, which utilizes a bit-wise technique and has an O(1) time complexity.

Space Complexity

The numPy library's implementation affects the code's space complexity. However, in the majority of situations, it may be regarded as O(1) since the code uses a fixed amount of memory regardless of the size of the input.

NOTE: The GCD (greatest common divisor) approach is a more effective way to get the LCM of huge numbers or numbers that are not quite prime. The formula below may be used to get the LCM of two integers using their GCD:

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

By using it recursively, this formula may be expanded to get the LCM of more than two integers.

Frequently Asked Questions

How to find LCM of 3 numbers in Python?

To find the Least Common Multiple (LCM) of three numbers in Python, you can calculate the LCM of the first two numbers, and then compute the LCM of the result and the third number using the lcm() function.

How to find LCM in programming?

In programming, you can find the Least Common Multiple (LCM) of two or more numbers using various approaches such as prime factorization, Euclidean algorithm, or using the built-in lcm() function in some programming languages. Choose the method that best suits your requirements and programming language capabilities.

Can LCM be negative?

LCM cannot be negative as it represents the smallest positive integer divisible by all given numbers. It's defined as an absolute value in mathematical contexts.

Can we find LCM of more than two numbers?

Yes, we can find the LCM of more than two numbers. LCM calculation extends to any number of integers, where the LCM is computed as the smallest common multiple of all given numbers.

Conclusion

Let's sum up by saying that the LCM of two or more integers may be calculated using a variety of different techniques in Python, including loop-based and GCD-based techniques. The approach chosen will depend on the magnitude of the numbers and the level of calculating efficiency needed. 

You can also read about:

We hope this blog has helped you enhance your knowledge of LCM in Python. Do visit here to study the Basics of Python with Data Structures and Algorithms in-depth and clarify all your concepts. 

Happy learning!

Previous article
Percentages
Next article
Speed, Distance and Time
Live masterclass