根据一个数的质因数分解，生成所有因子。

Question

如果你已经得到一个数的质因数分解，那么获取该数所有因数的最简单方法是什么？我知道可以从2循环到sqrt(n)来找到所有可被整除的数字，但既然我们已经有了质因数分解，这种方法似乎效率不高。

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

- dimo414

---

相关问题（Python）：https://dev59.com/03A65IYBdhLWcg3wxRk8 - tzot

请直接按升序枚举数字的因数，无需排序。详情请参见https://dev59.com/_V0a5IYBdhLWcg3wva16#30181351 - Will Ness

Answer 1

想象一下质因数就像是装在桶里的球。例如，如果你的数字的质因数为2、2、2、3和7，那么你可以取0、1、2或3个“2号球”，同样地，你可以取“3号球” 0或1次，“7号球”0或1次。

现在，如果你取两个“2号球”和一个“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);

- Nikita Rybak

---

只需知道n的值，无需了解其重复出现的次数。当“currentResult”能整除n时，持续将当前质数相乘。 - Sheldon L. Cooper

Answer 2

dimo414，生成因子通常被认为是一项非常困难的任务。实际上，大多数重要资产（例如钱、信息等）的保护，都依赖于一个简单但极其困难的任务——对数字进行分解。请参阅RSA加密方案的文章http://en.wikipedia.org/wiki/RSA_(cryptosystem)。不过我跑题了。

回答你的问题，组合方法是你最好的选择，正如Nikita所指出的那样（顺便说一句，你的解释很棒）。

许多人之所以会得出这个结论，是因为与生成质数相关的概念非常相似。不幸的是，这是错误的，因为你会错过几个大于sqrt(n)但不是质数的因子（我会让你自己证明这一点）。

现在，为了确定给定数字n的因子数量，我们需要看一下n的质因数分解。 如果n = p^a，那么我们知道n将有(a + 1)个因子（1, p, p², ... , p^a）。这是确定总因子数的关键。如果n有多个质因数，比如

n = p₁^a· p₂^b··· p_k^r

那么使用计数的乘法原理（http://en.wikipedia.org/wiki/Rule_of_product），我们知道将会有

m = (a + 1)·(b + 1)···(r + 1)

现在我们需要做的就是找到由质因数分解所给出的数字的所有可能组合。下面是一些在R中的代码，希望能够展示我所解释的内容。

我的代码的第一部分进行了一个简单的素性检查，因为如果这个数字是质数，那么唯一的因子就是1和它本身。接下来，如果这个数字不是质数且大于1，我首先找到这个数字的质因数分解，假设我们有：

n = p₁^a· p₂^b··· p_k^r

我然后只找到标记为UniPrimes的唯一质数，因此对于这个例子，UniPrimes将包含(p₁, p₂, p_k)。然后我找到每个质数的所有幂并将其添加到一个名为MyFactors的数组中。制作完此数组后，我查找MyFactors中元素的每个可能乘积组合。最后，我向数组添加1（因为它是一个微不足道的因数），并进行排序。哇！它非常快速，并且适用于具有许多因数的非常大的数字。

我尝试使代码尽可能易于翻译成其他语言（即，我假设您已经构建了生成质因数分解（或使用内置函数）和质数测试函数的函数）。我没有使用专业的R内置函数。如果有不清楚的地方，请告诉我。干杯！

factor2 <- function(MyN) {

    CheckPrime <- isPrime(MyN)

    if (CheckPrime == F && !(MyN == 1)) {
            MyPrimes <- primeFactors(MyN)
            MyFactors <- vector()
            MyPowers <- vector()
            UniPrimes <- unique(MyPrimes)
                    for (i in 1:length(UniPrimes)) {

                            TempSize <- length(which(MyPrimes == UniPrimes[i]))

                            for (j in 1:TempSize) {
                                    temp <- UniPrimes[i]^j
                                    MyPowers <- c(MyPowers, temp)
                            }

                    }
            MyFactors <- c(MyFactors, MyPowers)
            MyTemp <- MyPowers
            MyTemp2 <- vector()
            r <- 2
            while (r <= length(UniPrimes)) {

                    i <- 1L

                    while (i <= length(MyTemp)) {
                            a <- which(MyPrimes >  max(primeFactors(MyTemp[i])))
                                    for (j in a) {
                                            temp <- MyTemp[i]*MyPowers[j]
                                            MyFactors <- c(MyFactors, temp)
                                            MyTemp2 <- c(MyTemp2, temp)
                                    }
                            i <- i + 1
                    }
                    MyTemp <- MyTemp2
                    MyTemp2 <- vector()
                    r <- r + 1
            }
    } else {
            if (MyN == 1) {
                    MyFactors <- vector()
            } else {
                    MyFactors <- MyN
            }
    }
    MyFactors <- c(1, MyFactors)
    sort(MyFactors)
}

- Joseph Wood