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?

---

Idea

A problem of 'prime factor decomposition'. For example, 2520 is produced in such way:

from 2 to 10, initial list p is []

• 2 is prime, add 2 to p, p is [2] now
• 3 is prime, add 3 to p, p is [2, 3] now
• 4 is not prime, its prime factors are 2 * 2, one 2 in p, another needed, so add another 2 to p, p is [2, 3, 2] now
• 5 is prime, add 5 to p, p is [2, 3, 2, 5] now
• 6 is not prime, its prime factors are 2 * 3, both 2 and 3 are in p now, nothing need to do
• 7 is prime, add 7 to p, p is [2, 3, 2, 5, 7] now
• 8 is not prime, its prime factors are 2 * 2 * 2, two 2 in p, another needed, so add another 2 to p, p is [2, 3, 2, 5, 7] now
• 9 is not prime, its prime factors are 3 * 3, one 3 in p, another needed, so add another 3 to p, p is [2, 3, 2, 5, 7, 3] now
• 10 is not prime, its prime factors are 2 * 5, one 2 in p and one 5 in p, nothing need to do

so $$\prod p = 2520$$

Iterate from 2 to 20, gather all prime factors, add if any missing, then its product is result

---

from collections import Counter
from functools import reduce

def get_prime_factors(number):
    d = 2
    prime_factors = []
    while d ** 2 <= number:
        while number % d == 0:
            number //= d
            prime_factors.append(d)
        d += 1
    if number != 1:
        prime_factors.append(number)
    return prime_factors

get_prime_factors(4)

[2, 2]

get_prime_factors(10)

[2, 5]

get_prime_factors(24)

[2, 2, 2, 3]

get_prime_factors(11)

[11]

get_prime_factors(2)

[2]

def solve(end):
    counter = Counter()
    for i in range(2, end+1):
        for f, cnt in Counter(get_prime_factors(i)).items():
            counter[f] = max(counter[f], cnt)
    return reduce( lambda a, b: a * b, (f ** cnt for f, cnt in counter.items()), 1)

solve(10)

2520

solve(20)

232792560