Project Euler Problem 5 Solution

Project Euler Problem 5 Solution

Smallest multiple

by {BetaProjects} | Project Euler & HackerRank

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

Solving with Euclid’s GCD 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 to solve this problem is find the LCM for the integers {1, 2, 3, 4, …, 20} using Euclid’s GCD algorithm.

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

But wait, by 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 numeric carnage until our original list of {1…20} becomes the much smaller {11…20}. In general, all smaller factors of a bigger number in the list can be safely removed without changing the LCM, e.g., LCM(12,10,15,75) = LCM(12,10,75) = 300, as 15 is a factor of 75.

This reduces the number of factors to consider and helps to speed things up.

HackerRank version

HackerRank requires us to run 10 test cases for 1 ≤ N ≤ 40. No changes to the algorithm are required.

Python Source Code

from math import gcd
from functools import reduce
def LCM(a, b): 
    return a // gcd(a, b) * b
N = int(input("The LCM for numbers 1 through "))
print ("is", reduce(LCM, range(N//2+1, N+1)))	

Last Word

q = LCM(11,12)
for n in range(13,21):
    q = LCM(q,n)
print q