Project Euler Problem 5 Solution

Project Euler Problem 5 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

Finding the Least Common Multiple (LCM)

The Least Common Multiple (LCM) of a set of integers is the smallest positive number evenly divisible by every member of the set. To solve this problem for consecutive integers $\{1, 2, 3,\dots, 20\}$, we can use Euclid’s algorithm to compute the LCM efficiently.

Upon reflection, you'll realize that every number is divisible by $1$, so $1$ can be excluded.

Furthering this reasoning, we can eliminate other factors as well. 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 decimation until we are left with $\{11, 12, 13,\dots, 20\}$.

In general, when computing the LCM of a sequence of integers, smaller factors of larger numbers are redundant and can be excluded. For instance, the LCM of $\{12, 10, 15, 75\}$ is the same as the LCM of $\{12, 10, 75\}$, since $15$ is a factor of $75$.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 5

HackerRank Project Euler Problem 5 runs 10 test cases for $N$, where $1\le N\le 40$.

Python Source Code

import math, functools

for _ in range(int(input())):
    N = int(input())
    print(functools.reduce(math.lcm, range(N//2+1, N+1)))

Last Word

More reading and some applications for the LCM.
Python’s reduce(function, sequence [, initial value]) returns a single value constructed by calling the function LCM() on all the items in the sequence. Here’s the equivalent code without using reduce().

import math
LCM = lambda a, b: a // math.gcd(a, b) * b
q = LCM(11,12)
for n in range(13,21):
    q = LCM(q,n)
print(q)