查找数字的所有因式分解

Question

例如16可以这样表示：
2*2*2*2
4*2*2
4*4
8*2
（不包括普通情况 1*16）

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

因此，我需要像上面一样找到任何给定数字的所有表示形式。
首先，我能够使用以下代码得出给定数字的所有除数：

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.
    }
}

在此之后，我卡住了。我如何从所有除数得到所有想要的因式分解？
我能想到一个递归方法似乎有效但不知道如何实现它：

以16为例。让我们将查找 n 的所有表示的函数命名为 "Factor(n)"。 16 的所有非平凡因数都是 {2,4,8}。我们将 16 除以它的每个除数，得到 {8, 4, 2}。那么 Factor(16) = 2*Factor(8)、4*Factor(4) 和 8*Factor(8) 的并集。然而，这是我得到的。我是递归的新手，不确定这条路线是否可行。我需要一些关于如何把东西放在一起的帮助。

Answer 1

只要你不知道因子的个数，最有效的解决方案就是递归。

您将需要一个向量来存储当前路径：

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

和一个递归函数。
对于每次迭代，您尝试除以当前余数并记住：

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;
}

例如，假设我们有 8 个。这是它的工作原理：

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"

结果：
8,
4 * 2,
2 * 4,
2 * 2 * 2

现在，您看到了问题：[2 4] 和 [4 2] 是重复的答案。我们怎样才能避免重复答案？最简单的方法是仅按升序（降序，无所谓）顺序输出值。

让我们添加 max 变量并存储插入到路径中的最后一个数字，并仅查找那些小于或等于它的分隔符。例如，如果当前路径是 [2]，则递归不应该指向 [2 4]，而应该指向 [2 2]。 max 的初始值等于 value 因为路径中的第一个数字可以是任何数字。

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);
}

现在是这样运作的：

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"

结果：
8,
4 * 2,
2 * 2 * 2

一切正常！唯一看起来不正确的是“8”。它可能应该是“8 * 1”。您可以在输出中添加一行 if (path.size() == 1) cout << "1";。

结果：
8 * 1,
4 * 2,
2 * 2 * 2

这里是working Ideone demo.

我希望我没有让你更加困惑。第一次真的很难解释什么是递归。递归就像游泳或骑自行车——首先看起来很难。然后，你尝试并学习它，一旦你理解了它 - 你会想知道为什么你以前不能这样做 :) 祝你好运。

查找数字的所有因式分解

Find all factorizations of a number

c++

algorithm

factorization