Python Program to Find LCM

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)

You can also try this code with Online Python Compiler

Run Code

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

You can also try this code with Online Python Compiler

Run Code

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)

You can also try this code with Online Python Compiler

Run Code

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

You can also try this code with Online Python Compiler

Run Code

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

You can also try this code with Online Python Compiler

Run Code

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:

• HCF and LCM
   
• LCM of 2 numbers in C
   
• How to find GCD of Two Numbers in Python?
   

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!