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