Python Implementation of Problem 5

View source code here on GitHub!

Includes

Problem Solution

Project Euler Problem 5

I solved this problem by testing all combinations of the various multiples. I actually tried to solve this by hand before doing this, and it wasn't terribly hard. The answer turns out to be (2**4 * 3**2 * 5 * 7 * 11 * 13 * 17 * 19)

Problem:

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?

python.src.p0005.main() → int
 1"""
 2Project Euler Problem 5
 3
 4I solved this problem by testing all combinations of the various multiples. I
 5actually tried to solve this by hand before doing this, and it wasn't terribly
 6hard. The answer turns out to be (2**4 * 3**2 * 5 * 7 * 11 * 13 * 17 * 19)
 7
 8Problem:
 9
102520 is the smallest number that can be divided by each of the numbers from 1
11to 10 without any remainder.
12
13What is the smallest positive number that is evenly divisible by all of the
14numbers from 1 to 20?
15"""
16from functools import reduce
17from itertools import combinations
18from operator import mul
19
20
21def main() -> int:
22    group = range(1, 21)
23    answer = 1_000_000_000_000
24    for x in group:
25        for multiples in combinations(group, x):
26            num = reduce(mul, multiples, 1)
27            if num < answer and all(num % divisor == 0 for divisor in group):
28                answer = num
29    return answer

Tags: divisibility, factorization