// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (27 votes, average: 5.00 out of 5)

Project Euler Solutions

Project Euler 5 Solution

Project Euler 5 Solution

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?

Project Euler 5 Analysis

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:


Prime Factors


Prime Factors















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.

Project Euler 5
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.
download arrowUse this link to get the Project Euler 5 Solution Python 2.7 source.


  • 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


2 Responses to “Project Euler 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.


    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:

      I won’t bother putting in the commas.

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

Post a comment