On Wed, Nov 14, 2012 at 12:52 PM, Selby Rowley Cannon
<selbyrowleycan...@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
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
