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

想象一下，素除数是桶中的球。例如，如果你的数字的素数除数是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);

dimo414，生成因子一般被认为是一项非常艰巨的任务。事实上，保护您的大多数重要资产（即金钱，信息等）都取决于简单但极其困难的分解数字任务。请参阅有关 RSA 加密方案 http://en.wikipedia.org/wiki/RSA_（密码系统）的文章。我说点题外话。

为了回答你的问题，正如Nikita所指出的那样，组合方法是你最好的方法（顺便说一句，对你的解释赞不绝口）。

我知道我可以从2循环到sqrt（n）并找到所有可整除的数字

许多人跳到这个结论，因为与生成素数相关的概念非常相似。不幸的是，这是不正确的，因为你会错过几个大于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)
}