Problem Description

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?

Analysis

Just find the least common multiple for the integers {2, 3, 4, …, 20} using Euclid’s algorithm.

Solution

Runs < 1 second in Python.

def gcd(a,b): 
  return b and gcd(b, a % b) or a
 
def lcm(a,b): 
  return a * b / gcd(a,b)
 
n = 1
for i in range(2, 21):
    n = lcm(n, i)
print "Answer to PE5 = ",n

Comments