1 Replies - 517 Views - Last Post: 07 January 2013 - 06:47 PM Rate Topic: -----

#1 Mr909  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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. :nottalkingtoyou:

Is This A Good Question/Topic? 0
  • +

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

#2 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10560
  • View blog
  • Posts: 39,071
  • 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.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1