java - 给定素数分解，生成一个数的所有因数

Question

如果您已经对一个数进行了质因式分解，那么获得该数的所有因式的最简单方法是什么？我知道我可以从 2 循环到 sqrt(n) 并找到所有可整除的数字，但这似乎效率低下，因为我们已经有了素数分解。

我想它基本上是组合/选择函数的修改版本，但我似乎只能找到计算组合数量的方法，以及计算因子数量的方法，而不是实际生成组合/因子.

Answer 1

想象素数除数是桶里的球。例如，如果您的数字的主要因数是 2、2、2、3 和 7，那么您可以取 0、1、2 或 3 个“球 2”的实例。同样，你可以拿 'ball 3' 0 或 1 次和 'ball 7' 0 或 1 次。

现在，如果你拿 'ball 2' 两次和'ball 7' 一次，你得到除数 2*2*7 = 28。同样，如果你不拿球，你得到除数 1，如果你拿所有球，你得到除数 2*2*2*3*7 等于数字本身。

最后，要从桶中取出所有可能的球组合，您可以轻松地使用递归。

void findFactors(int[] primeDivisors, int[] multiplicity, int currentDivisor, long currentResult) {
    if (currentDivisor == primeDivisors.length) {
        // no more balls
        System.out.println(currentResult);
        return;
    }
    // how many times will we take current divisor?
    // we have to try all options
    for (int i = 0; i <= multiplicity[currentDivisor]; ++i) {
        findFactors(primeDivisors, multiplicity, currentDivisor + 1, currentResult);
        currentResult *= primeDivisors[currentDivisor];
    }
}

现在你可以在上面的例子中运行它了:

findFactors(new int[] {2, 3, 7}, new int[] {3, 1, 1}, 0, 1);