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

Learn More

To learn more, feel free to reach out to me @yujian_tang on Twitter, connect with me on LinkedIn, and join our Discord. Remember to follow the blog to stay updated with cool Python projects and ways to level up your Software and Python skills! If you liked this article, please Tweet it, share it on LinkedIn, or tell your friends!

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

I started my professional software career interning for IBM in high school after winning ACSL two years in a row. I got into AI/ML in college where I published a first author paper to IEEE Big Data. After college I worked on the AutoML infrastructure at Amazon before leaving to work in startups. I believe I create the highest quality software content so that’s what I’m doing now. Drop a comment to let me know!

One-Time
Monthly
Yearly

Make a one-time donation

Make a monthly donation

Make a yearly donation

Choose an amount

$5.00
$15.00
$100.00
$5.00
$15.00
$100.00
$5.00
$15.00
$100.00

Or enter a custom amount

$

Your contribution is appreciated.

Your contribution is appreciated.

Your contribution is appreciated.

DonateDonate monthlyDonate yearly

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

Leave a Reply

%d bloggers like this: