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

[Oscar Benjamin]

On Aug 13, 2013 7:21 PM, "Peter Otten" <__peter__ at 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 at python.org
> To unsubscribe or change subscription options:
> http://mail.python.org/mailman/listinfo/tutor
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/tutor/attachments/20130813/47e75444/attachment-0001.html>