005 - evenly divisible

See Problem 5.

"Evenly divisible" is a strange turn of phrase, but Wikipedia, tells me that it just means divisible without remainder.

A brute force approach serves for solving this: we can start at a low bound and increment it, until we find a number that is divisible by all within a given set. Also our set doesn't have to be 1 to 20 inclusive: we can disregard all numbers below 10 because they are inferred by larger numbers. (That is, if a number is divisible by 18, it implies a number is divisible by 9 and so on.). We can generalise the solution to:

set_max = 20L
l = range (set_max/2 + 1, set_max+1)
start = set_max


while True:
        checked_all_divs = True
        for i in l:
                if start % i:
                        checked_all_divs = False
                        break
        if (checked_all_divs):
                print start
                break
        else:
                start += 1

In plain English: set_max is the maximum of the range (20 in this case). We then construct l the list of necessary divisors from half this range and up. Then we start at the lowest possible solution, the maximum of the range. We test every divisor against the current solution until one fails, and then increment by one. If it doesn't fail, it must be our solution.

This is surprisingly slow: numbers up to 15 complete almost instantly and then performance starts to suck badly. 17 is slow but achievable (12,252,240). 20 completes after 5-10 minutes (232,792,560). As Project Euler says that no solution should take longer than a minute, we need a shortcut. The obvious one, that speeds the algorithm up by a factor of 20, can be done by changing the final line to:

start += set_max