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?
The question can be rephrased as “What is the least common multiple of the numbers from 1 to 2?”
This number is not the same as the product of 1 to 20. The LCM of 1, 2, 3 and 4 is 12, not 24, because the number 2 is already accounted for in the number 4.
Recall the rule that the product of two numbers is the product of their GCD and their LCM. We can use this rule to compute the LCM, by multiplying numbers from 1 to 20, and at each step, dividing the product by the LCM of the product and the next multiplier.
In the case of 1, 2, 3, and 4, this would work as follows.
- 1 x 2 = 2. GCD is 1. So LCM = 2/1 = 2.
- 2 x 3 = 6. GCD is 1. So LCM = 6/1 = 6.
- 6 x 4 = 24. GCD of 6 and 4 is 2. So LCM = 24/2 = 12.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
def gcd(a, b): x = max(a, b) y = min(a, b) while x % y != 0: z = x % y x = max(y, z) y = min(y, z) return y # Initialize the product to 1. Multiply by numbers from 2 to 20 product = 1 for i in range(2, 21): product = product * i // gcd(product, i) print(product) |