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.
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.