Get all factors of a number (iterators showdown :)

Question

You are given all the prime factors of a number, along with their multiplicities (highest powers).
The requirment is to produce all the factors of that number.

Let me give an example:

Prime factors:

• 2 (power: 3)
• 3 (power: 1)

(meaning the number is 2^3 * 3^1 = 24)

The expected result is:
1, 2, 3, 4, 6, 8, 12, 24

I'm thinking of doing this (in C#) with some chained custom iterators, one for each prime factor, that would count from 0 to the power of that prime number.

How would you implement this? Use your preferred language.

This is related to problem #23 from Project Euler

Answer 1

I first shoot without an IDE at hand so there might be some errors in there.

struct PrimePower
{
    public PrimePower(Int32 prime, Int32 power) : this()
    {
        this.Prime = prime;
        this.Power = power;
    }

    public Int32 Prime { get; private set; }
    public Int32 Power { get; private set; }
}

And then just this recursive function.

public IEnumerable<Int32> GetFactors(IList<PrimePowers> primePowers, Int32 index)
{
    if (index < primePowers.Length() - 1)
    {
        Int32 factor = 1;
        for (Int32 p = 0; p <= primePowers[index].Power; p++)
        {
            yield return factor * GetFactors(primePowers, index + 1);
            factor *= primePowers[index].Prime;
        }
    }
    else if (index = primePowers.Length() - 1)
    {
        Int32 factor = 1;
        for (Int32 p = 0; p <= primePowers[index].Power; p++)
        {
            yield return factor * GetFactors(primePowers, index + 1);
            factor *= primePowers[index].Prime;
        }
    }
    else
    {
        throw new ArgumentOutOfRangeException("index");
    }
}

It could also be an extension method and IList<PrimerPower> could probably weakened to IEnumerable<PrimePower> with a few Skip() and Take() calls. I don't like passing the index around, too, but the alternative would be copying the prime power list for each call. In consequence I think a iterative solution would be preferable - going to add one if I have an IDE again.

Answer 2

Consider all possible combinations of powers. For each combination, raise the primes to their corresponding power, and multiply the result.

>>> from functools import reduce
>>> from itertools import product, starmap
>>> from operator import mul 
>>> 
>>> def factors(prime_factors):
...     primes, powers = zip(*prime_factors)
...     power_combos = product(*(range(p + 1) for p in powers))
...     prime_combos = (zip(primes, c) for c in power_combos)
...     return (reduce(mul, starmap(pow, c)) for c in prime_combos)
... 
>>> sorted(factors([(2, 3), (3, 1)]))
[1, 2, 3, 4, 6, 8, 12, 24]

This code uses Python 3.0. Aside from the call to sorted, it makes use of iterators exclusively.

Side remark: too bad this question seems to be rather unpopular. I would like to see e.g. some functional solutions being posted. (I may attempt to write a Haskell solution later.)

Answer 3

If you do not care about the single divisors, but about the sum of all divisors of n you might want to have a look at the Divisor Function:

Thus the sum of the divisors of

is