鉴于其主要分解，生成数量的所有因素

Question

如果您已经有一个数字的主要分解，那么获得该数字的所有因素的最简单方法是什么？我知道我可以从2循环到SQRT（n）并找到所有可分配的数字，但这似乎效率低下，因为我们已经有了主要分解。

我想这基本上是组合 /选择功能的修改版本，但是我似乎发现的只是计算组合数量的方法，以及计算因子数量的方法，而不是实际生成组合 /因素。

Answer 1

想象一下，主要的除数是桶中的球。例如，如果您的数字的主要除数为2、2、2、3和7，那么您可以将“ Ball 2”的0、1、2或3个实例进行。同样，您可以服用“ 3'0或1次球”，而“球7” 0或1次。

现在，如果您将“ 2'2”和“球7”进行一次，那么您会得到除数2*2*7 = 28。 *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);

Answer 2

Dimo414，生成因子通常被认为是非常困难的任务。实际上，保护您的大多数重要资产（即金钱，信息等），基于简单但非常困难的考虑数字的任务。请参阅有关RSA加密方案的本文 http://en.wikipedia.org/wiki/rsa_(Cryptosystem）. 。我离题。

为了回答您的问题，正如Nikita所指出的那样，组合方法是您的最佳方法（BTW，您的解释中的荣誉）。

我知道我可以从2循环到SQRT（n）并找到所有可分配的数字

由于与生成素数相关的非常相似的概念，许多人就得出了这个结论。不幸的是，这是不正确的，因为您会错过比SQRT（N）大的几个因素（我会让您向自己证明这一点）。

现在，为了确定任何给定数字n的因素数量，我们研究了 n. 。如果 n = p^一种, ，那么我们知道n将有（A + 1）因素（1，p，p², ，...，P^一种）。这是确定因素总数的关键。如果 n 有多个主要因素，说

n = p₁^一种· 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₁^一种· p₂^b··· p_k^r

然后，我只发现独特的素数躺着 单次， 因此，在此示例中，uniprimes将包含（p₁, ，p₂, ，p_k）。然后，我找到每个素数的所有功能，然后将其添加到累积的数组中 myfactors。 制作此阵列后，我发现myFactor中元素的所有可能产品组合。最后，我在数组中添加1个（因为这是一个微不足道的因素），然后对其进行排序。瞧！它非常快，可以适用于很多因素。

我试图使代码尽可能翻译成其他语言（即，我认为您已经构建了一个生成质量分解（或使用内置功能）和质数测试功能的函数。）而且我没有' t使用。干杯!

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