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

Generating all factors of a number given its prime factorization

提问by dimo414

If you already have the prime factorization of a number, what is the easiest way to get the set of all factors of that number? I know I could just loop from 2 to sqrt(n) and find all divisible numbers, but that seems inefficient since we already have the prime factorization.

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

I imagine it's basically a modified version of a combinations/choose function, but all I can seem to find is methods for counting the number of combinations, and ways of counting the number of factors, not to actually generate the combinations / factors.

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

回答by Nikita Rybak

Imagine prime divisors are balls in a bucket. If, for example, prime divisors of your number are 2, 2, 2, 3 and 7, then you can take 0, 1, 2 or 3 instances of 'ball 2'. Similarly, you can take 'ball 3' 0 or 1 times and 'ball 7' 0 or 1 times.

想象素数除数是桶中的球。例如，如果您的数字的质因数是 2、2、2、3 和 7，那么您可以取 0、1、2 或 3 个“球 2”的实例。同样，您可以选择“ball 3” 0 或 1 次和“ball 7” 0 或 1 次。

Now, if you take 'ball 2' twice and 'ball 7' once, you get divisor 2*2*7 = 28. Similarly, if you take no balls, you get divisor 1 and if you take all balls you get divisor 2*2*2*3*7 which equals to number itself.

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

And at last, to get all possible combinations of balls you can take from the bucket, you could easily use recursion.

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

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

Now you can run it on above example:

现在你可以在上面的例子上运行它：

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

回答by Joseph Wood

dimo414, generating factors is generally considered a very difficult task. In fact, the protection of most of your important assets (i.e. money, info., etc.), rest on the simple, yet extremely difficult task of factoring a number. See this article on the RSA encryption scheme http://en.wikipedia.org/wiki/RSA_(cryptosystem). I digress.

dimo414，生成因子通常被认为是一项非常艰巨的任务。事实上，保护您的大部分重要资产（即金钱、信息等），依赖于简单但极其困难的分解数字的任务。请参阅这篇关于 RSA 加密方案的文章http://en.wikipedia.org/wiki/RSA_(cryptosystem)。我离题了。

To answer your question, a combinatorial approach is your best method as pointed out by Nikita (btw, kudos on your explanation).

为了回答您的问题，正如 Nikita 指出的那样，组合方法是您最好的方法（顺便说一句，对您的解释表示敬意）。

I know I could just loop from 2 to sqrt(n) and find all divisible numbers

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

Many people jump to this conclusion because of the very similar concept associated with generating primes. Unfortunately, this is incorrect, as you will miss several factors greater than the sqrt(n) that aren't prime numbers (I'll let you prove this to yourself).

由于与生成素数相关的概念非常相似，许多人会得出这个结论。不幸的是，这是不正确的，因为您会遗漏几个大于 sqrt(n) 的非质数因子（我会让您自己证明这一点）。

Now, to determine the number of factors for any given number n, we look to the prime factorization of n. If n = p^a, then we know that n will have (a + 1) factors (1, p, p², ... , p^a). This is the key to determining the total number of factors. If nhad multiple prime factors, say

现在，以确定的因素，对于任何给定数量的数n，我们期待的因式分解ñ。如果n = p ^a，那么我们知道 n 将有 ( a + 1) 个因子 ( 1, p, p ², ... , p ^a)。这是确定因子总数的关键。如果n有多个质因数，说

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

n = p ₁ ^a ·p ₂ ^b ...p _k ^r

then using the Product Ruleof counting (http://en.wikipedia.org/wiki/Rule_of_product), we know that there will be

然后使用计数的乘积规则（http://en.wikipedia.org/wiki/Rule_of_product），我们知道会有

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

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

factors. Now, all we need to do is find every possible combination of the numbers given to us by the prime factorization. Below, is some code in R, which hopefully demonstrates what I have explained.

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

The first part of my code does a simple check of primality because if the number is prime, the only factors are 1 and itself. Next, if the number isn't prime and greater than 1, I first find the prime factorization of the number, say we have,

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

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

n = p ₁ ^a ·p ₂ ^b ...p _k ^r

I then find only the unique primes labled UniPrimes,so for this example, UniPrimes would contain (p₁, p₂, p_k). I then find all powers of each prime and add it to an array labled MyFactors.After this array is made, I find every possible product combination of the elements in MyFactors. Lastly, I add 1 to the array (as it is a trivial factor), and sort it. Voila! It is extremely fast and works for very large numbers with many factors.

然后我只找到标记为UniPrimes的唯一素数，因此对于此示例，UniPrimes 将包含 ( p ₁, p ₂, p _k)。然后我找到每个素数的所有幂，并将其添加到一个标记为MyFactors的数组中。在创建这个数组之后，我会在 MyFactors 中找到元素的所有可能的乘积组合。最后，我将 1 添加到数组中（因为它是一个微不足道的因素），并对其进行排序。瞧！它非常快，适用于具有许多因素的非常大的数字。

I tried to make the code as translatable as possible to other languages (i.e. I assume that you have already built a function that generates the prime factorization (or using a built-in function) and a prime number test function.) and I didn't use specialized built-in functions unique to R. Let me know if something isn't clear. Cheers!

我试图使代码尽可能可翻译为其他语言（即我假设您已经构建了一个生成素数分解（或使用内置函数）和素数测试函数的函数。）但我没有'不要使用 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)
}