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
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 functionLCM()
on all the items in the sequence. Here’s the equivalent code without usingreduce()
.
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)