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
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 String Slicing
- Build a Scientific Calculator in Python
- Build a Neural Network from Scratch in Python 3
- Web Scraping with Python
- How to Send an Email with an Attachment in Python
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.