(27 votes, average: 5.00 out of 5)

## Project Euler 5: Find the smallest number divisible by each of the numbers 1 to 20

#### Project Euler 5 Problem Description

Project Euler 5: 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?

### Euclid’s algorithm

The smallest positive number that is evenly divided (divided without remainder) by a set of numbers is called the Least Common Multiple (LCM). All we have to do is find the LCM for the integers {1, 2, 3, 4, …, 20} using Euclid’s algorithm.

After some reflection you might realize correctly that every integer is divisible by 1, so 1 can be removed from the list and calculate 2 through 20.

But by furthering this reasoning and we can eliminate other factors. We leave 20 in the calculation but then remove its factors {2, 4, 5, 10}. Any number evenly divisible by 20 is also evenly divisible by these factors. 19 is prime and has no factors – it stays. 18 has factors {2, 3, 6, 9} and we already removed 2 but we can remove 3, 6, and 9. 17 is prime – it stays too.

We continue this numeric carnage until our original list of {1..20} becomes the much smaller {11, 12, 13, 14, 15, 16, 17, 18, 19, 20}. Following this reasoning, the lower half of the set is completely irrelevant and can be eliminated from consideration without changing the result.

```from fractions import gcd
def lcm(a, b):
return a // gcd(a, b) * b

L = 20
print 'LCM of all numbers from 1 through', L, 'is', reduce(lcm, range(L//2+1, L+1))
```

### A better method for this problem

For larger ranges, say greater than 105, this method becomes very slow. The method outlined below can adeptly handle larger sets such as {2, 3, 4, …, 106}.

Taking 20 as our example, we know the LCM must be divisible by every prime less than or equal to 20. In this case those primes are {2, 3, 5, 7, 11, 13, 17, 19}. For the primes less than square root of 20 there may be an exponent involved, and for those greater than the square root of 20 the exponent will always be 1. Let’s look at the breakdown:

Number

Prime Factors

Number

Prime Factors
11

11

16

24
12

22×3

17

17
13

13

18

2×32
14

2×7

19

19
15

2×5

20

22×5
Now, using the greatest exponent of each prime, multiply them together as:
24 × 32 × 5 × 7 × 11 × 13 × 17 × 19 = 232,792,560.
We use the log function to determine the exponent of the prime, p, as log(20)/log(p) by looping through the primes.

For example, the floor of (log 20 / log 2) = 4; the largest exponent of 2 in the prime factors (24 = 16). Again, the floor of (log 20 / log 3) = 2; the largest exponent of 3 in the prime factors (2×32=18).

The HackerRank version ups the limit for 1 ≤ n ≤ 40 and runs up to 10 consecutive test cases. This algorithm handles those test cases in less than a hundredth of a second.

This program and method
solves all test cases for
Project Euler 5 on HackerRank

#### Project Euler 5 Solution

Runs < 0.001 seconds in Python 2.7.
Use this link to get the Project Euler 5 Solution Python 2.7 source.

#### Afterthoughts

• Notes on Python usage:
The statement: `from Euler import prime_sieve` includes a function for calculating prime numbers from our Euler.py library 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 corrected it only has to be done once and is reflected in the scripts that import it. This keeps scripts short and concise. Function `prime_sieve` is listed in Common Functions and Routines for Project Euler.

• In the GCD version we changed `return a * b / gcd(a,b)` to `return a / gcd(a,b) * b`. “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).” [from Wikipedia]

• Python’s `reduce`(function, sequence, initial value) returns a single value constructed by calling the binary function `mul` on the first two items of the sequence, then on the result and the next item and so on.

• The code shown below removes the use of reduce to achieve the same results.
```a = 1
for p in primes:
a*= p**int(log(L)/log(p))
```

Project Euler 5

Project Euler 5 Solution last updated

## Discussion

### 4 Responses to “Project Euler 5 Solution”

1. #include
using namespace std;
#define ll long long
int main()
{
int t , n ;
cin>>t;
while( t– )
{
cin>>n;
ll lcm = 1;
for( ll i = 2 ;i <= n ; i++ )
{
lcm = (i*lcm)/(__gcd(lcm,i));
}
cout<< lcm <<endl;
}
return 0;
}

Posted by Rayhan | July 30, 2020, 7:54 AM
2. I recently come across this and it is fast.

Your code is concise and beauty. But I could not understand.

def factor_finder(n, j=2):

factor_list=[]

if n == 2:
return [2]
elif n == 3:
return [3]
else:
while n >= j*2:
while n % j == 0:
n = int(n/j)
factor_list.append(j)
j += 1

if n > 1:
factor_list.append(n)

return factor_list
def smallest_multiples(n):

factor_list = []
final_list = []

for i in range(2, n+1):
factor_list += (factor_finder(i))
#print(factor_list)

for i in set(factor_list):
l1 = []
l2 =[]
for j in factor_list:
if j == i:
l1.append(j)
else:
if len(l1) > len(l2):
l2 = l1
l1= []
else:
l1 = []
#print(l2)
final_list += l2
#print(final_list)

return np.array(final_list).cumprod()[-1]

Posted by Yongqing Cao | December 12, 2018, 7:06 PM
3. 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