[Tutor] Real LCM

[Danny Yoo]

On Wed, 18 Jul 2001, Timothy M. Brauch wrote:

> I finally have the gcd and lcm for any length list of numbers.  The code
> is as appears below...
> 
> ----------------------------------------------------------
> def __gcd__(a,b):
>     if b==0:
>         return a
>     return __gcd__(b,a%b)
> 
> def gcd(list):
>     list.sort()
>     g=list[0]
>     for i in range(len(list)):
>         g=__gcd__(g,list[i])
>     return g

Small warning: try to avoid using "list" as the name of a variable: it
conflicts with a builtin function with the same name:

###
>>> list
<built-in function list>
>>> list("this is a test")
['t', 'h', 'i', 's', ' ', 'i', 's', ' ', 'a', ' ', 't', 'e', 's', 't']
###


There's another neat way to get the gcd of a list of numbers: since you
have something that can gcd() two numbers together, you can combine this
with the reduce() function:

###
>>> def __gcd__(a, b):
...     if b == 0: return a
...     return __gcd__(b, a%b)
...
>>> def gcd(L): return reduce(__gcd__, L)
...
>>> gcd([10, 20, 40, 80])
10
>>> gcd([75, 35])
5
###


Magic.  *grin*  reduce() isn't as usless as it might first appear, but it
does take some practice to see what it's good for.

Hope this helps!