Tuesday, 21th July, 2009
Project Euler 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?
Well, this is finding the Lowest common multiple of the numbers 1 - 20. So we calculate lcm(1,2), lcm((lcm(1,2)),3) … etc. until we’ve computed all of the lowest common multiples upto 20.
So this one can be attacked in a fairly number theoretic way, using Euclid’s greatest common divisor algorithm, and the lowest common multiplier. This means we’ll be using reduce() :-)
def gcd(a, b): while (b != 0): a, b = b, a%b return a reduce(lambda x,y: ((x*y)/gcd(x,y)), range(1,21))
Notice the lambda. Now usually I recommend against trying to use Python’s lambda construct. It’s very weak compared to Scheme’s or Lisp’s; and often you’ll be wanting to do something outside it’s functionality; but in this case, it’s the perfect fit.
Done! :-D