5: Smallest multiple#

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 positive number that is evenly divisible by all of the numbers from 1 to 20?

Submit your answer

Your Solution#

Lunch this notebook and try to create your own solution!

Tip: look for the launch button (🚀) in the top right corner!

def problem5(N, M): # numbers from N to M
    # Try your solution here
    return solution

# Testing:
unittest.main(argv=[''], verbosity=2,exit=False)

# Printing Project Euler Solution
# print(problem5(1,20))

My solution#

Spoiler Alert!!

See my solution bellow

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 positive number that is evenly divisible by all of the numbers from 1 to 20?

Brute Force#

This took almost 10 minutes in my pc for N=1 and M=20. It is not a good solution.

Can we do better?

def problem5(N,M):
    divisors = np.arange(N,M+1)

    i = M
    while not all(i%divisors == 0):
        i += 1
    return(i)

Using prime factorization#

According Wikepedia, we can calulating the LCM using a prime factorization approach.

Consider the example with numbers 48 and 180. The prime factorization is:

  • \(48 = 2*2*2*2*3 = 2^4*3^1\)

  • \(180 = 2*2*3*3*5 = 2^2*3^2*5^1\)

The LCM is:

\[LCM = 2^{max(4,2)}*3^{max(1,2)}*5^{max(0,1)}\]
\[LCM = 2^{4}*3^{2}*5^{1)}\]
\[LCM = 16*9*5\]
\[LCM = 720\]

So we can follow some steps:

  • find prime factors

  • find the maximum number of every prime factor

  • apply the prime^max rule to calculate LCM

def get_factors(N):
    factors=[]
    i = 2 # first prime
    while (N > 1.0): # test if the number was factored to 1
        if N % i == 0: # check remainder
            N /= i # update the value
            factors.append(i)
        else:
            i += 1 # try a new divisor
    return factors

def problem5(N,M):
    factors = [get_factors(i) for i in range(N, M)] # get list of factors for every input
    primes = set(sum(factors, [])) # get unique primes

    lcm = 1
    for p in primes:
        n = max(f.count(p) for f in factors) # get the maximum number of repetitions for every prime
        lcm *= p**n
    return lcm

# Testing
unittest.main(argv=[''], verbosity=2,exit=False)

Add main question:

# Printing Project Euler Solution
problem5(1,20)

232792560