[Mr909]

So, I have this function I found that gives lists of prime factors. So, in order to find the least common denominator of a and b, what I should do is just take whatever is in common between the two factor lists, and then multiply it by itself.

I also realized it would be really neat to have a function that simply does that, takes two lists and only gives the larger quantity for each item.

To start, here's the code I found:

#This lovely patch of code was found in Dhananjay Nene's blog.
#http://blog.dhananjaynene.com/2009/01/2009-is-not-a-prime-number-a-python-program-to-compute-factors/
#Original Name: factor

def prime_factors(n):
        if n == 1: return [1]
        i = 2
        limit = n**0.5
        while i <= limit:
                if n % i == 0:
                        ret = factor(n/i)
                        ret.append(i)
                        return ret
                i += 1

        return [n]

Now, say I wanted the least common denominator of prime_factors(64) and prime_factors(34).

prime_factors(64)=[2, 2, 2, 2, 2, 2]
prime_factors(32)=[17, 2]

The content list would contain one instance of 17, six instances of 2 (not seven). Multiply everything in that list together, it would return the numeric least common denominator.

Any advice? I cringe at list problems; They've also been most of what I've been dealing with.

[macosxnerd101]

Check out the Euclidean algorithm as an O(log n) solution.