My Python Solution to Find the LCM
Another “fun” challenge
Do you remember middle school math (I do — it was my favorite class!) and finding the LCM (least common multiple) of two or more numbers? Classic 6th-grade stuff and it’s one of the “very hard” challenges on Edabyte. This is my take on how to solve the challenge of finding the LCM for a list of numbers. There are many different ways to solve this problem, but I used prime factorization. For review, prime factorization is when you list the prime factors of the numbers, then multiply together each factor the greatest number of times it occurs.
As a simple example, let’s start with 3 and 4:
3 = 3 ^ 1 and 4 = 2 ^ 2The LCM of 3 and 4 is then:
(3 ^ 1) * (2 ^ 2) or 12Now, what happens if we up the ante? The LCM of 6 and 8 would be 24 (prime factorization of 6 is 2 ^ 1 x 3 ^ 1 and 8 is 2 ^ 3 for a result of 2 ^ 3 * 3 ^ 1 or 24). For more entertainment, let’s try lists of numbers.
numbers1 = [4, 6, 8, 10, 15]numbers2 = [13, 6, 17, 18, 19, 20, 37]
There are several different ways that this can be coded. Admittedly, my solution is not the most elegant; this is just the way I did it and the new tricks I learned about Python along the way.
The first step was to write a short function to find the prime factors of a number. Pretty straight-forward:
Next, after lots of googling, I came across the Counter in Python. Counter() is a container found in the Collections module, is a subclass of dictionary, and tracks how many times equivalent values are used.
With the use of Counter(), I was able to find the greatest number of times a prime factor was used. Here’s how it’s incorporated into the main function to find the LCM of a list of numbers:
Can you imagine trying to find the LCM of 13, 6, 17, 18, 20, and 37 using non-computer methods? That would be really too much, even for a math nerd.
