# Trying to get the least common denominator of a pair of lists.

Page 1 of 1

## 1 Replies - 1021 Views - Last Post: 07 January 2013 - 06:47 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=306029&amp;s=5abc0533535c1782cfa338ccc2679868&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 Mr909

Reputation: 0
• Posts: 3
• Joined: 19-December 12

# Trying to get the least common denominator of a pair of lists.

Posted 07 January 2013 - 06:45 PM

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.

Is This A Good Question/Topic? 0

## Replies To: Trying to get the least common denominator of a pair of lists.

### #2 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12316
• Posts: 45,416
• Joined: 27-December 08

## Re: Trying to get the least common denominator of a pair of lists.

Posted 07 January 2013 - 06:47 PM

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