What is the smallest number that has all the numbers from 1 to 20 as factors? Or, what is the Least Common Multiple (LCM) of 1 to 20?
Solution
The simplest solution would be to start from 1 and test each number for factors 1 to 20. This works, but is very expensive - we would need to check 20n factors, where n is the smallest number for which all numbers from 1 to 20 are factors. Although we don’t know in advance what n will be, its upper limit is 20! (i.e. 20 x 19 x 18 …), which is a huge number. Factorisation is also expensive, as it often involves a division instruction (some can be converted to shifts or multiplications).
Our first question therefore is: how do we reduce the search space from 1..20! to a more manageable size? There are two main changes we can make.
Only check multiples of the highest factor. Only multiples of x will have x as a factor. In this particular example our largest factor is 20, so we only need to check every 20th number (20, 40, 60, …). Any numbers in between will not have 20 as a factor, and therefore we do not need to test any of the other factors either. This simple observation reduces the search space by 95%, as we only need to check 5% (1 in every 20) of the numbers.
Only check the top half of the factors list. If we split the list of factors in half, we end up with (1 to 10) and (11 to 20). Each element in the first set is a factor of at least one element in the second set (2 is a factor of 12, 3 is a factor of 12, 4 is a factor of 16 etc.) If a number, f, is a factor of another number, f’, then any number which has f’ as a factor will also have f as a factor. For example, if we know that 16 is a factor of 32, then we know that 2, 4 and 8 are also factors of 32, because they are factors of 16. This means that we only have to check the second set of factors, reducing the number of checks by 50%.
If we combine these two methods, we reduce the number of calculations from 20n to n (95% reduction) and then to n/2 (50% reduction), or 2.5% of our simplest solution.
package main
import "fmt"
func main() {
const highestFactor = 20
const lowestFactor = 11
const requiredFactorCount = 9
smallestNumber := 0
for currentNumber := highestFactor; smallestNumber == 0; currentNumber += highestFactor {
currentFactorCount := 0
for currentFactor := lowestFactor; currentFactor < highestFactor; currentFactor++ {
if currentNumber%currentFactor == 0 {
currentFactorCount++
} else {
break
}
}
if currentFactorCount == requiredFactorCount {
smallestNumber = currentNumber
}
}
fmt.Println(smallestNumber)
}This takes 0.18s to run on my machine.