Problem 5:

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?

A solution:

from math import ceil

def factorize(num):
    powers = []
    limit = int(ceil(float(num)/2)) # we only need to look up to num/2 for factors
    for i in range(2, limit+1):
        while num % i == 0: # ie, if i is a factor of num
            powers.append(i)
            num = num/i # take factor out of num and continue with smaller num
    if len(powers) == 0: # haven't found any factors, ie, num is prime
        powers.append(num)
    return powers

topnum = 20
master_factors = []
total = 1
for i in range(2,topnum+1):
    current_factors = factorize(i)
    while len(current_factors) != 0:
        fact = current_factors[0]
        count_difference = current_factors.count(fact)-master_factors.count(fact)
        if count_difference > 0:
            for j in range(count_difference): master_factors.append(fact)
        del current_factors[0:current_factors.count(fact)]

for i in range(len(master_factors)): total *= master_factors[i]

print total

This code seems pretty messy, there’s surely better ways to write it. For sure, the factorize function should be changed so that it only checks odd numbers (after two), that would get rid of half the iterations. After solving the problem I looked through the forum for ways others were solving it, and found this one written in Python, from user tenigmanogo:

def gcd(a, b):
while b != 0:
a, b = b, a % b
return a

def lcm(a, b):
return a*b/gcd(a, b)

print reduce(lcm, range(1, 20+1))

Definitely makes me want to learn more, and get better about looking at problems in different ways. It’s so simple! Though, with the longer solution, I now have a function that will find the prime factors of a number, which will come in handy for future problems.