#### 11 Jun 2011 maragato»(Master)

Euler 5

So the other night I was a bit bored and decided to do something to pass the time. I first came across Project Euler a while ago, but had never gone further than problem #1. Boredom is a great motivator and I went through problems #2 thru #9 last night and I decided to post my solutions in search of better ones. Feel free to comment with your suggestions.

Project Euler’s Problem #5 statement is –

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?

My first attempt was using brute force, but it didn’t go very well. It took a considerable amount of time, so I decided to think about the problem a bit. In the end, it boils down to the a relation between the lesser common multiplier and the greater common divisor.

 ```1 2 3 4 5 6 7 8 9 10 11 12 ``` ```def gcd(a, b):         if b== 0: return a         return gcd(b, a % b)   def lcm(a, b):         return a * b / gcd(a, b)   if __name__ == "__main__":         b = 2         for i in range(3,20):                 b = lcm(b, i)         print b```

While the original code took several seconds before I killed it, this runs in 0.015s.

Syndicated 2010-08-03 17:30:36 from Roberto Teixeira's blog