Select Page

Project Euler 5 Problem Statement

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?

Solution

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 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, xrange(L//2+1, L+1))

A better method for this problem

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

Again, taking the LCM of {1,20}, 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.
To find the exponent of the prime number we use the log function as log(20)/log(p) for each prime, p, in the set above.

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).

HackerRank version

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

Python 2.7 Source

Last Word

We require our prime sieve and include it by importing it into our program:

from Euler import prime_sieve

The external function are in the REPL.IT file Euler.py. This keeps scripts short and concise.

Python’s reduce(function, sequence, initial value) returns a single value constructed by calling the binary function mul on all the items in the sequence.

The code shown below does the same thing without using reduce.

a = 1
for p in primes:
    a*= p**int(log(L)/log(p))