(5 votes, average: 4.20 out of 5)

## Project Euler Problem 5 Solution

#### 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

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

#### Solution

Runs < 1 second in Python.

```from Euler import gcd   def lcm(a,b): return a / gcd(a,b) * b   print "Answer to PE5 = ", reduce(lcm, range(2,21))```

Notes on Python usage:

• The statement: `from Euler import gcd` includes a function for calculating the GCD from our Euler.py module into the program. Many useful functions can be imported this way without copying its definition into each program. When an improvement is made or an error is corrected it only has to be done once and is reflected in the scripts that import it. This keeps scripts short and concise. The `gcd` function is listed on the tools page.
• We changed `return a * b / gcd(a,b)` to `return a / gcd(a,b) * b`. [from Wikipedia] “Because gcd(a, b) is a divisor of both a and b, it’s more efficient to compute the LCM by dividing before multiplying. This reduces the size of one input for both the division and the multiplication, and reduces the required storage needed for intermediate results (overflow in the a×b computation).”
• In order to exploit the benefits of the reduce function, we changed the code:
```n = 2
for i in range(2, 21):
n = lcm(n, i)
```

to: `reduce(lcm, range(2,21))`
reduce(function, sequence) returns a single value constructed by calling the binary function lcm on the first two items of the sequence (2,3), then on the result and the next item (6,4), and so on(12,5). Both ways give the same results.

## Discussion

### 2 Responses to “Project Euler Problem 5 Solution”

1. Hi Mike,

I once calculated the smallest number divisible by every number between 1 and 100. I posted this on my facebook profile back in 2009.

69,720,375,229,712,477,164,53​3,808,935,312,303,556,800 is the smallest number divisable by every number from 1 to 100. I calculated this on 4-3-2003.

Scott

Posted by Scott Murphy | July 16, 2011, 4:32 PM
• I ran this program to 100 and confirmed your result. For 1 to 1000 it is:
7128865274665093053166384155714272920668358861885893040452001991154324087
5811114994764441519138715869117178170195752565129802640676210092514658710
0430513107268626814320019660997486274593718834370501543445252373974529896
3145674982128236956232823794011068809262317708861979540791247754558049326
4757378299233527517967352480424636380511370343312147817468508784534856780
21888075373249921995672056932029099390891687487672697950931603520000

I won’t bother putting in the commas.

Posted by Mike | July 18, 2011, 1:17 AM