math - need divisors algorithm

[Philp Smith]

excellent - thanks
in the meantime I managed to write something myself which
a)    works
b)    looks reasonably elegant and pythonic
but
c)   is recursive
d)  requires a mainroutine and co-routine

I have a feeling if I analysed it it would prove to be relatively 
inefficient as I'm sure it creates a lot of temporary objects (partial 
lists)

So I will gratefully try your version - and for interest's sake post mine at 
some point (its on other computer) for comment.

Phil

"Tim Peters" <tim.peters at gmail.com> wrote in message 
news:mailman.1111.1112246542.1799.python-list at python.org...
> [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.