'Coding has over 700 languages', '67% of programming jobs aren’t in the technology industry', 'Coding is behind almost everything that is powered by electricity'
Last Updated: Jun 30, 2023
Easy

LCM in Python

Author Surbhi Sharma
0 upvote
gp-icon
Aptitude preparation
Free guided path
9 chapters
99+ problems
gp-badge
Earn badges and level up

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. 

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
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

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.

LCM in Python using Loops

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

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.

Limitations of using Loops to Find LCM

Although the loop-based approach to finding LCM is straightforward and uncomplicated, it has certain drawbacks. 

  1. Given that iterating over all the numbers until the LCM is discovered could not be effective for locating the LCM of huge numbers. 
     
  2. Finding the LCM of non-relatively prime numbers may also take longer.

LCM in Python using 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

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).

LCM 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

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

Can LCM be negative?

No, LCM is always positive.

Can we find LCM of more than two numbers?

Yes, LCM can be found for any number of integers using the same methods as for two integers.

What is the relationship between LCM and GCD?

LCM and GCD are related by the formula LCM(a,b) x GCD(a,b) = a x b.

What is the LCM of 0 and a non-zero number?

The LCM of 0 and a non-zero number is always 0.

Can we use the numPy library to find the LCM of more than two numbers?

Yes, the numPy library provides a lcm.reduce() function that can be used to find the LCM of multiple numbers. This function takes an iterable (such as a list or tuple) of integers as input and returns the LCM of all the integers in the iterable.

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. 

To learn more about DSA, competitive coding, and many more knowledgeable topics, please look into the guided paths on Coding Ninjas Studio. Also, you can enroll in our courses and check out the mock test and problems available. Please check out our interview experiences and interview bundle for placement preparations.

Happy learning!

Previous article
Percentages
Next article
Speed, Distance and Time
Guided path
Free
gridgp-icon
Aptitude preparation
9 chapters
190+ Problems
gp-badge
Earn badges and level up
Live masterclass