[Tutor] Real LCM

[Danny Yoo]

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

> It appears the search on Python.org is not working, at least I haven't
> been able to do a search on the site for a few days.
> 
> I was wondering if there is a function somewhere in Python to find the
> Least Common Multiple of two numbers.  Or, should I try to hack
> together something.

Hmmm... I can't think of one that's built into the Python library.  
Neither is there a gcd() (greatest common divisor) function that's built
in.  However, there's great algorithm by the mathematician Euclid called
"Euclid's Algorithm" that calculates gcd's very quickly.  Really quickly:

###
def gcd(a, b):
    if b == 0: return a
    return gcd(b, a % b)
###

Euclid's algorithm is really useful, especially for rationalizing
fractions.  Anyway, I did a quick lookup on google for the topic of "gcd's
and lcm's", and got back this page:

    http://www.geocities.com/zabrodskyvlada/aat/a_eucl.html


The gcd() and lcm() are related: if we get the GCD of two numbers, getting
their lcm() is really easy:

    "lcm(a, b) = a * b / gcd(a, b)"

The Python code for this reads very closely to the math.


Hope this helps!