Search code examples
pythonpython-itertools

pythonic way of getting the list of divisors given prime factorization

I have the prime factorization as a dictionary:

>>>pf(100)
>>>{2:2,5:2}

What is the best pythonic way for retrieving all the divisors of the number using the function pf? feel free to use itertools.

Solution

  • Something like this maybe

    >>> from itertools import *
>>> from operator import mul
>>> d = {2:2,5:1} # result of pf(20)
>>> l = list(chain(*([k] * v for k, v in d.iteritems())))
>>> l
[2, 2, 5]
>>> factors = set(chain(*(permutations(l, i) for i in range(1,len(l)+1))))
set([(2, 2, 5), (2,), (5,), (5, 2, 2), (2, 2), (2, 5), (5, 2), (2, 5, 2)])
>>> set(reduce(mul, fs, 1) for fs in factors)
set([4, 2, 10, 20, 5])