# Project Euler Solution 5: Smallest multiple

This is part of the Project Euler series, this is about Problem 5: Smallest multiple. It is about finding a smallest common multiple of 20 numbers.

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?

What we are essentially looking for is the smallest common multiple of all the numbers from 1 to 20. This means that we need to find a number such that it contains at least all the prime factors that each of these numbers have. For this I will implement three steps:

We need a function which dissembles a number into its prime factors and their multiplicities. For 20 this would be 2² × 5¹. In Python I can express this as a `{2: 2, 5: 1}`

. The function uses the prime generator from Solution 3: Largest prime factor.

def get_prime_factors(number: int) -> dict[int, int]: factors = collections.defaultdict(lambda: 0) for prime in prime_generator(): while number % prime == 0: factors[prime] += 1 number /= prime if number == 1: break return factors

Then I need something which merges two dicts of prime factors such that it takes the union of the factors and the maximum in the multiplicities. This is done here:

def merge_factors(factors_1: dict[int, int], factors_2: dict[int, int]): for factor, count_2 in factors_2.items(): count_1 = factors_1.get(factor, 0) factors_1[factor] = max(count_1, count_2)

Now I can just start with an empty dictionary of factors and go through all the numbers from 1 to 20. I compute the prime factors and then merge them with the factors that I already have.

def solution_factor_dicts() -> None: factors = {} for i in range(1, 21): new_factors = get_prime_factors(i) merge_factors(factors, new_factors) result = 1 for factor, count in factors.items(): result *= factor**count return result

When going up to 10, it takes 18 µs to get the answer of 2,520. This means that the code likely is correct. Up to 20 it takes 46 µs to get the answer 232792560. This seems to be fast enough.