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 Solution

This is a bit longer than it needs to be, but it should run rather quickly.

import time   # function to factor a given positive integer n def factors(n): factors = [] # remove any factors of 2 first while n % 2 == 0: factors.append(2) n = n/2 # now look for odd factors p = 3 while n != 1: while n % p == 0: factors.append(p) n = n/p p += 2 return factors   # merge two lists of factors based on maximum multiplicities def factor_append(factors,new): if len(factors) == 0: return new for i in range(len(new)): if i > 0 and new[i] == new[i-1]: continue new_count = new.count(new[i]) old_count = factors.count(new[i]) if new_count > old_count: for j in range(new_count - old_count): factors.append(new[i]) factors.sort() return factors   # find the smallest positive evenly divisible number for a positive integer n def smallest_evenly_divisible(num): F = [] for i in range(1,num + 1): F = factor_append(F,factors(i)) product = 1 for i in F: product *= i return product   start = time.time() product = smallest_evenly_divisible(20) elapsed = (time.time() - start)   print "result %s returned in %s seconds." % (product,elapsed)

And, it does run rather quickly.

result 232792560 returned in 0.000357866287231 seconds.

### One Trackback

1. [...] we come across the 10,001st prime. (This will be slow. We’ll make a faster version later.) In Project Euler Problem 5 we had a cheap (and inefficient) factorization routine. We’ll use that here. import time [...]