[Tutor] LCM

[eryksun]

On Wed, Nov 14, 2012 at 12:52 PM, Selby Rowley Cannon
<selbyrowleycannon at ymail.com> wrote:
>
>     I've been trying to write a function to find the Lowest Common Multiple
> of two numbers, but it isn't working and I've kinda hit a dead end on the
> thought-process end of things.

Since the LCM is the smallest multiple of both numbers, you want to
factor out what they have in common from one of them:

    x = x_unique * gcd
    y = y_unique * gcd
    lcm = x_unique * y_unique * gcd
        = (x / gcd) * y

For example, say you have x = 21 = 3*7 and y = 35 = 5*7. The factor in
common, i.e. the greatest common divisor (GCD), is 7. So the LCM is
105 = 3*5*7.

I'm sure you can search for a good GCD algorithm with no problem since
it's over 2,000 years old. But there's an "implementation" (it's not
much work) in the fractions module:

    >>> 21 / fractions.gcd(21, 35) * 35
    105

    >>> print inspect.getsource(fractions.gcd)
    def gcd(a, b):
        """Calculate the Greatest Common Divisor of a and b.

        Unless b==0, the result will have the same sign as b (so that when
        b is divided by it, the result comes out positive).
        """
        while b:
            a, b = b, a%b
        return a