Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.1k views
in Technique[技术] by (71.8m points)

algorithm - Python factorization

I'd just like to know the best way of listing all integer factors of a number, given a dictionary of its prime factors and their exponents.
For example if we have {2:3, 3:2, 5:1} (2^3 * 3^2 * 5 = 360)
Then I could write:

for i in range(4):
  for j in range(3):
    for k in range(1):
      print 2**i * 3**j * 5**k

But here I've got 3 horrible for loops. Is it possible to abstract this into a function given any factorization as a dictionary object argument?

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)

I have blogged about this, and the fastest pure python (without itertools) comes from a post by Tim Peters to the python list, and uses nested recursive generators:

def divisors(factors) :
    """
    Generates all divisors, unordered, from the prime factorization.
    """
    ps = sorted(set(factors))
    omega = len(ps)

    def rec_gen(n = 0) :
        if n == omega :
            yield 1
        else :
            pows = [1]
            for j in xrange(factors.count(ps[n])) :
                pows += [pows[-1] * ps[n]]
            for q in rec_gen(n + 1) :
                for p in pows :
                    yield p * q

    for p in rec_gen() :
        yield p

Note that the way it is written, it takes a list of prime factors, not a dictionary, i.e. [2, 2, 2, 3, 3, 5] instead of {2 : 3, 3 : 2, 5 : 1}.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...