Find all factorizations of a number

Question

For example, 16 can be expressed in these ways:
2*2*2*2
4*2*2
4*4
8*2
(excluding the trivial case 1*16)

36:
2*2*3*3
2*2*9
2*18
4*3*3
12*3
4*9

Therefore, I need to find all the representations of any given number just like above.
To start, I was able to come up with all the divisors of a given number with the codes below:

void FindDivisors(int n)
{
    vector<int> my_vector;
    for (int i = 2; i < n/2 + 1; i++)
    {
        if (n % i == 0)
            my_vector.push_back(i); //store divisors in a vector.
    }
}

After this, I got stuck. How do I get from all the divisors to all the factorizations wanted?
I can think of a recursion method that seems to work but do not exactly know how to implement it:

Take 16 as the example. Let's name the function to find all the representations of n to be "Factor(n)". All non-trivial divisors of 16 are {2,4,8}. We divide 16 by each of its divisor and get {8, 4, 2}. Then Factor(16) = the union of 2*Factor(8), 4*Factor(4) and 8*Factor(8). However, this is as far as I got. I am new to recursion and not sure if this route works out. I need some help on how to put things together.

Answer 1

As long as you don't know the number of factors, the most effective solution is recursion.

You will need a vector to store the current path:

vector<int> path; // it will store all current factors

and a recursive function.
For every iteration you try to divide current remainder and remember:

void OutputRec(int value)
{
    if (value == 1) // We have divided the whole number
    {
        for (int i = 0; i < path.size(); i++) cout << path[i] << " ";
        cout << endl;
        return;
    }

    for (int i = value; i > 1; i--)
    {
        if (value % i == 0) { // if it is divisible
            path.push_back(i); // add to path
            OutputRec(i, value / i); // continue working
            path.pop_back(); // remove from path
        }
    }
}

void Output(int value)
{
    cout << "Result for " << value << ": " << endl;
    path = vector<int>();
    OutputRec(value);
}

int main() {
    Output(4);
    Output(16);
    Output(36);
    Output(256);

    return 0;
}

For example, let we have 8. Here is how it works:

OutputRec(8), path = []:
    i = 8: divisible (8 / 1 = 1)
        OutputRec(1), path = [8], value == 1 > output "8".
    i = 7, 6, 5: not divisible
    i = 4: divisible (8 / 4 = 2)
        OutputRec(2), path = [4]:
            i2 = 2: divisible (2 / 2 = 1)
                OutputRec(1), path = [4 2], value == 1 > output "4 2".
    i = 3: not divisible
    i = 2: divisible (8 / 2 = 4)
        OutputRec(4), path = [2]:
            i3 = 4: divisible (4 / 4 = 1)
                OutputRec(1), path = [2 4], value == 1 > output "2 4".
            i3 = 3: not divisible
            i3 = 2: divisible (4 / 2 = 2)
                OutputRec(2), path = [2 2]:
                    i4 = 2: divisible (2 / 2 = 1)
                        OutputRec(1), path = [2 2 2], value == 1 > output "2 2 2"

Result:
8,
4 * 2,
2 * 4,
2 * 2 * 2

Now, you see the problem: [2 4] and [4 2] is duplicated answer. How can we avoid duplicating answers? The easiest approach is to output values only in ascending (descending, does not matter) order.

Let's add max variable and store the last number inserted into a path and find only those dividers which are less or equal to it. For example, if current path is [2], then the recursion shouldn't go for [2 4], but should go for [2 2]. The initial value of max is equal to value as the first number in the path can be any.

void OutputRec(int max, int value)
{
    if (value == 1) {
        for (int i = 0; i < path.size(); i++) cout << path[i] << " ";
        if (path.size() == 1) cout << "1";
        cout << endl;
        return;
    }

    for (int i = max; i > 1; i--) // loop from max. Min(max, value) would be better
    {
        if (value % i == 0) {
            path.push_back(i);
            OutputRec(i, value / i);
            path.pop_back();
        }
    }
}

void Output(int value)
{
    cout << "Result for " << value << ": " << endl;
    path = vector<int>();
    OutputRec(value, value);
}

Here is how it works now:

OutputRec(8), path = []:
    i = 8: divisible (8 / 8 = 1)
        OutputRec(1), path = [8], value == 1 > output "8".
    i = 7, 6, 5: not divisible
    i = 4: divisible (8 / 4 = 2)
        OutputRec(2), path = [4]:
            i2 = 2: divisible
                OutputRec(1), path = [4 2], value == 1 > output "4 2".
    i = 3: not divisible
    i = 2: divisible (8 / 2 = 4)
        OutputRec(4), path = [2]:
            // notice i3 starts from 2, because last inserted is 2
            i3 = 2: divisible (4 / 2 = 2)
                OutputRec(2), path = [2 2]:
                    i4 = 2: divisible (2 / 2 = 1)
                        OutputRec(1), path = [2 2 2], value == 1 > output "2 2 2"

Result:
8,
4 * 2,
2 * 2 * 2

Everything works fine! The only thing which looks incorrect is "8". It probably should be "8 * 1". You can add a line like if (path.size() == 1) cout << "1"; to the output.

Result:
8 * 1,
4 * 2,
2 * 2 * 2

Here is the working Ideone demo.

I hope that I didn't confuse you even more. It is really difficult to explain what recursion is at the first time. Recursion is like swimming or cycling - it looks difficult first. Then, you try it and learn it, and once you understand it - you will wonder why couldn't you do this before :) Good luck.