Super Simple Python: Two Ways to Get LCM

Super Simple Python is a series of Python projects you can do in under 15 minutes. In this episode, we’ll be covering two ways to get the Least Common Multiple (LCM) of two numbers in under 10 lines of Python each!

We’ve covered a lot of different kinds of programs in the Super Simple Python series. We’ve covered programs using the random library like the Password Generator, functional programs like the Unit Convertor, and math programs like the Prime Factorizer. This one falls in the math category.

We’re going to cover:

  • What is a Least Common Multiple?
  • How to do LCM with GCD
  • How to do Iterative LCM in Python
  • Testing our LCM Functions

What is the Least Common Multiple?

The Least Common Multiple of two numbers is the smallest number that is divisible by both numbers. There are a few ways to calculate this. For this post we’re going to cover two of the simplest ways to calculate this. The first way we’ll go over is by calculating the product of both numbers and dividing by their Greatest Common Denominator. The second way is to iteratively add the smallest number to itself until we reach a number that is divisible by the larger number.

LCM with GCD in Python

In a recent Super Simple Python post, we covered how to get the Greatest Common Denominator. For this example, we’ll use the recursive GCD function to calculate our LCM. To do this we’ll first create a recursive GCD function. That function will take two integers as input and recursively calculate the GCD. 

Our LCM function will also take two integers as parameters. It will simply return the product of the two inputs divided by the GCD. I wrap this in an int() function simply to make the return look pretty, otherwise it will return a float trailing with .0. Another way to do this is to use the integer divide operator, // instead of /.

def gcd(x: int, y: int):
    if y == 0:
        return x
    return gcd(y, x%y)
 
def lcm_w_gcd(x: int, y: int):
    return int(x * y/gcd(x, y))

Iterative LCM in Python

To iteratively calculate the LCM we will also need two parameters. We could enforce that x must always be bigger than y or vice versa, but we won’t. We’ll simply start off the function by finding which one of them is larger. Once we know which number is larger, we start off our Least Common Multiple with the smaller number and iteratively add the smaller number to it until the sum is divisible by the larger number. Finally, we return that number as the LCM.

def iterative_lcm(x: int, y: int):
    if x < y:
        small = x
        big = y
    else:
        small = y
        big = x
    lcm = small
    while lcm % big != 0:
        lcm += small
    return lcm

Testing

I’ve prepared three test cases for us to test with both functions. I’ve commented the expected output next to each number.

print(lcm_w_gcd(27, 3)) # 27
print(lcm_w_gcd(15, 55)) # 165
print(lcm_w_gcd(21, 99)) # 693
 
print(iterative_lcm(27, 3)) # 27
print(iterative_lcm(15, 55)) # 165
print(iterative_lcm(21, 99)) # 693

When we run the function we get output like the image below, as expected.

Python Least Common Multiple (LCM) Output
Python Least Common Multiple Output

Further Reading

I run this site to help you and others like you find cool projects and practice software skills. If this is helpful for you and you enjoy your ad free site, please help fund this site by donating below! If you can’t donate right now, please think of us next time.

Yujian Tang

One thought on “Super Simple Python: Two Ways to Get LCM

Leave a Reply

%d bloggers like this: