Reconstructing a list of divisors from the prime factors (recursively)

Question

I have a list of the prime factors of a number in the following form: int[] factors = {number of factors,factor1,poweroffactor1,factor2,poweroffactor2,...};

I want to get the equivalent of dynamically nested for loops that will yield all the factors, where the for loops will look something like this:

int currentpod = 1;
for(int i=0;i<factors[2];i++)
{
    currentprod *= Math.Pow(factors[1],i);
    for(int j=0;j<factors[4];j++)
    {
         currentprod *= Math.Pow(factors[3],i);
         ...
         //When it hits the last level (i.e. the last prime in the list, it writes it to a list of divisors
         for(int k=0;k<factors[6];k++)
         {
              divisors.Add(Math.Pow(factors[5],k)*currentprod);
         }
    }
}

Unfortunately, this code blows up as currentprod does not get reset enough. Here is the actual code that I am using to try an accomplish this:

        public static List<int> createdivisorlist(int level, List<int> factors, int[] prodsofar,List<int> listsofar)
    {
        if (level == factors[0])
        {
            prodsofar[0] = 1;
        }
        if (level > 1)
        {
            for (int i = 0; i <= 2*(factors[0]-level)+1; i++)
            {
                prodsofar[level-1] = prodsofar[level] * (int)Math.Pow(factors[2 * (factors[0] - level) + 1], i);
                listsofar =  createdivisorlist(level - 1, factors, prodsofar, listsofar);
            }
        }
        else
        {
            for (int i = 0; i <= factors.Last(); i++)
            {
                listsofar.Add(prodsofar[level] * (int)Math.Pow(factors[2 * (factors[0] - level) + 1], i));
                if (listsofar.Last() < 0)
                {
                    int p = 0;
                }
            }
            return listsofar;
        }
        return listsofar;
    }

the original arguments are: level = factors[0] factors = a list of the prime factors in the format specified above prodsofar[] = all elements are 1 listsofar = an empty list

How can i reset prodsofar so that it does not "blow up" and instead just does what I outlined? Note: as a test, use 2310, as under the current code, the divisor to be added is negative (int overflow).

Answer 1

The idea of the recursive algorithm you have in mind is to keep an accumulating list of divisors. For that, the following code is an example of how to do it (retaining your notation: since "divisors" and "factors" mean exactly the same thing, the multiple terminology is unfortunate):

public static List<int> divisors(int[] factors, List<int> foundfactors, int level)
{
    if(level > factors[0]) return foundfactors;

    int current = 1;
    List<int> curpowers = new List<int>();
    for(int i=0; i<factors[2*level]+1; ++i)
    {
        curpowers.Add(current);
        current *= factors[2*level-1];
    }
    List<int> newfactors = new List<int>();
    foreach(int d in foundfactors)
        foreach(int n in curpowers)
            newfactors.Add(d*n);
    return divisors(factors, newfactors, level + 1);
}

Call it with something like

    // 600 = 2^3 * 3^1 * 5^2
    int[] pfactors = new int[] {3, 2,3, 3,1, 5,2};
    List<int> foundfactors = new List<int> {1};
    List<int> ds = divisors(pfactors, foundfactors, 1);
    foreach(int d in ds) Console.WriteLine(d);

which prints all 24 divisors of 600.