On Aug 13, 2013 7:21 PM, "Peter Otten" <__pete...@web.de> wrote: > > 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().
I think it's better to compute the lcm by finding its prime factorisation. E.g. There are 4 twos in it since that's the maximum number of twos in the prime factorisation of any of the integers up to 20. I would post a snippet but isn't it generally a bit of a faux-pas to give solutions to these problems (I mean this as a real question)? Oscar > > _______________________________________________ > Tutor maillist - Tutor@python.org > To unsubscribe or change subscription options: > http://mail.python.org/mailman/listinfo/tutor
_______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
