Generating all factors of a number given its prime factorization

Question

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.

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.

Answer 1

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.

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.

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

Answer 2

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.

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

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

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

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 n had multiple prime factors, say

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

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

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.

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,

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.

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!

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