Relationship between Least Common Multiple and Greatest Common Factor
Never realized this before. Kind of cool.
def gcd(a, b):
pfa = prime_factors(a)
pfb = prime_factors(b)
common = set(pfa) & set(pfb)
return reduce(operator.mul, [i ** min(pfa.count(i), pfb.count(i)) for i in common])
def lcm(a, b):
'''Get the least common multiple of two numbers.'''
pfa = prime_factors(a)
pfb = prime_factors(b)
common = set(pfa) & set(pfb)
return reduce(operator.mul, [i ** max(pfa.count(i), pfb.count(i)) for i in common])
This is why all CIS students should take number theory.
Mish
2011/07/01 at 22:32
also this shows why lcm(a,b) = ab/gcd(a,b)
Chao Xu
2011/10/23 at 06:32