LCM By Division MethodFirst, write the numbers, separated by commas. Now divide the numbers, by the smallest prime number. If any number is not divisible, then write down that number and proceed further. Keep on dividing the row of numbers by prime numbers, unless we get the results as 1 in the complete row.
I read an interesting DailyWTF post today, "Out of All The Possible Answers..." and it interested me enough to dig up the original forum post where it was submitted. This got me thinking how I would solve this interesting problem - the original question is posed on Project Euler as:
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?
To reform this as a programming question, how would you create a function that can find the Least Common Multiple for an arbitrary list of numbers?
I'm incredibly bad with pure math, despite my interest in programming, but I was able to solve this after a little Googling and some experimenting. I'm curious what other approaches SO users might take. If you're so inclined, post some code below, hopefully along with an explanation. Note that while I'm sure libraries exist to compute the GCD and LCM in various languages, I'm more interested in something that displays the logic more directly than calling a library function :-)
I'm most familiar with Python, C, C++, and Perl, but any language you prefer is welcome. Bonus points for explaining the logic for other mathematically-challenged folks out there like myself.
EDIT: After submitting I did find this similar question Least common multiple for 3 or more numbers but it was answered with the same basic code I already figured out and there's no real explanation, so I felt this was different enough to leave open.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With