How to Solve a Problem 6: Smallest Common Multiple
Recently, I came across this question on /r/learnprogramming Question: 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 positive number that is evenly divisible by all of the numbers from 1 to 20? Well, how would you write a program to figure this out? The answer is not that difficult, but it involves a lot of prime numbers. The short version: we can "construct" the number by starting from 1 and work our way up to 20. 1 is obviously 1 2 is obviously 2 3 however, will be 6, as it needs to be divisible by 2 and 3 4 however, is NOT 24, but 12, 5 is 60 6 is 60 because 60 is already divisible by 6 7 is 420 8 is 840 (remember, factors) 9 is 2520 10 is still 2520. Do you see a pattern? Let's say you need to calculate smallestMultiple of X. To get it, you need the PREVIOUS smallestMultiple. i.e. smallestMultiple(X-1). For simplicity, let's call it "prevSM" If that is divisible by