[Philp Smith]
Does anyone have suggested code for a compact, efficient, elegant, most of
all pythonic routine to produce a list of all the proper divisors of an
integer (given a list of prime factors/powers)
If the canonical factorization of N is the product of p_i**e_i, the
number of divisors is the product of e_i+1. This can be
astronomically large, so it's important to minimize the number of
multiplications performed, and to write a generator to produce the
divisors (it may, e.g., be impossible to materialize a list of all of
them).
This one's easy and efficient:
def gen_divisors(prime_list):
elts = sorted(set(prime_list))
numelts = len(elts)
# Split on the number of copies of elts[i].
def gen_inner(i):
if i >= numelts:
yield 1
return
thiselt = elts[i]
thismax = prime_list.count(thiselt)
# powers <- [thiselt**i for i in range(thismax+1)],
# but using only thismax multiplications.
powers = [1]
for j in xrange(thismax):
powers.append(powers[-1] * thiselt)
for d in gen_inner(i+1):
for prime_power in powers:
yield prime_power * d
for d in gen_inner(0):
yield d
For example, do:
for d in gen_divisors([2, 3, 2, 3, 2, 3, 5, 2, 3]):
print d
You're on your own for the "proper" business; try not to use more than
one line to do it <wink>.
I find recursion clearest here. An iterative version is easy enough
to do by incrementing from 0 thru product(e_i) (and just skipping the
endpoints if you really want "proper") in a mixed-radix system defined
by the e_i. Exercise for the reader.
Harder: generate divisors in increasing order.
