[Tutor] [Spoiler alert] Re: To find the least number divisible by all numbers from 1-20

[Peter Otten]

Peter Otten wrote:

> I'll post a naive implementation of that idea in a follow-up.

So there:

def gcd(a, b):
    if a == b:
        return a
    elif a > b:
        return gcd(a-b, b)
    else:
        return gcd(a, b-a)

N = 20
numbers = range(2, N+1)
while len(numbers) > 1:
    numbers.sort()
    a, b = numbers[:2]
    d = gcd(a, b)
    numbers[:2] = [a*b//d]
result = numbers[0]
assert all(result % i == 0 for i in range(1, N+1))
print result

It turns out I can only avoid the recursion limit by sorting the numbers and 
picking the smallest. For greater N you need to come up with a smarter 
approach (the actual limit was N<=48) or at least a non-recursive 
implementation of gcd().