How to get all the factors of a number using its prime factorization?

Question

For example, I have the number $420$. This can be broken down into its prime factorization of $$2^2 \times3^1\times5^1\times7^1 = 420 $$

Using $$\prod_{i=1}^r (a_r + 1)$$ where $a$ is the magnitude of the power a prime factor is raised by and $r$ is the number of prime factors. I get $24$ possible factors.

Is there an easy way to iterate through all those $4$ factors to obtain all $24$? I know this can be easily done using a table with numbers with only $2$ factors. But, as this one has $4$ I obviously can't implement the table method. So any general solution to do this? Thanks!

Answer 1

Expand the following expression: $$(2^0+2^1+2^2)(3^0+3^1)(5^0+5^1)(7^0+7^1)$$ Each combination of four choices (e.g. $2^2, 3^1, 5^0, 7^1$, whose product is $2^23^15^07^1=84$) gives a distinct factor of $420$.

Answer 2

By way of example of a table of factors, just to check we're talking about the same thing:

The factors of $8=2^3$ are of course just $2^0, 2^1, 2^2, 2^3$ or calculated out $1,2,4,8$.

The factors of $9=3^2$ are $3^0, 3^1, 3^2$ aka $1,3,9$.

Now the factors of $72$ can be made up by combining two numbers chosen, one from each of these two sets:

\begin{array}{c|ccc} \times & 1 & 2 & 4 & 8 \\\hline 1 & 1 & 2 & 4 & 8 \\ 3 & 3 & 6 & 12 & 24 \\ 9 & 9 & 18 & 36 & 72 \\ \end{array}

This is no doubt the kind of table you are thinking of.

For $420$ we could apply this process repeatedly, just feeding the contents of each table into one axis of the next table:

\begin{array}{c|ccc} \times & 1 & 2 & 4 \\\hline 1 & 1 & 2 & 4 \\ 3 & 3 & 6 & 12 \\ \end{array}

\begin{array}{c|ccc} \times & 1 & 2 & 4 & 3 & 6 & 12 \\\hline 1 & 1 & 2 & 4 & 3 & 6 & 12 \\ 5 & 5 & 10 & 20 & 15 & 30 & 60 \\ \end{array}

\begin{array}{c|ccc} \times & 1 & 2 & 4 & 3 & 6 & 12 & 5 & 10 & 20 & 15 & 30 & 60 \\\hline 1 & 1 & 2 & 4 & 3 & 6 & 12 & 5 & 10 & 20 & 15 & 30 & 60\\ 7 & 7 & 14 & 28 & 21 & 42 & 84 & 35 & 70 & 140 & 105 & 210 & 420\\ \end{array}

or for a slightly more attractive final table we could split the factors into more equal subsets, here the factors of $2^23^1 =12$ across the top and the factors of $5^17^1=35$ down the side.

\begin{array}{c|ccc} \times & 1 & 2 & 4 & 3 & 6 & 12 \\\hline 1 & 1 & 2 & 4 & 3 & 6 & 12 \\ 5 & 5 & 10 & 20 & 15 & 30 & 60\\ 7 & 7 & 14 & 28 & 21 & 42 & 84 \\ 35 & 35 & 70 & 140 & 105 & 210 & 420\\ \end{array}

Answer 3

Well... yeah. They are all the numbers that are in the form $2^a3^b5^c7^d$ where $0 \le a \le 2; 0 \le b\le 1; 0 \le c\le 1;0 \le d\le 1;$

Just list them all:

$2^03^05^07^0 = 1$

$2^13^05^07^0 = 2$

$2^23^05^07^0 = 4$

$2^03^15^07^0 =3$

$2^13^15^07^0 =6$

....etc...

Less typing: they are $1,2,4,3,6,12,5,10,20,15,30,60,7,14,28,21,42,84,35,70,140,105,210,420$

In general if $N=\prod p_i^{k_i}$ just list every possible $\prod p_i^{m_i}$ where for each $m_i$ $0\le m_i \le k_i$.

Answer 4

If $n = \prod_{i=1}^r p_i^{a_i} $ is the prime factorization on $n$, there are $\prod_{i=1}^r (a_i + 1) $ prime factors.

Look at this as counting a $r$-digit number in a variable base, with the base of the $i$-th digit being $a_i+1$, so that digit goes from $0$ to $a_i$. If $b_i$ is the $i$-th digit, then the value corresponding to that digit is $p_i^{b_i}$.

Here is my take on a moderately efficient algorithm to compute all the possible factors. The divisor starts at $1$. When a digit is incremented, the value of the divisor is multiplied by $p_i$. If the $i$-th digit exceeds $a_i$, it is set to zero, the divisor divided by $p_i^{a_i}$, and the next digit is examined.

Initialize $d = 1$ (the divisor) and $b_i = 0$ and $c_i = p_i^{a_i}$ for $i=1$ to $r$ (the exponents and max powers of $p_i$).

$\text{do forever}\\ \quad\text{output } d\\ \quad\text{for }i=1\text{ to }r\\ \qquad \text{if } b_i<a_i\text{ then } b_i=b_i+1; d=d\cdot p_i; \text{ exit for loop} \quad\text{(digit did not overflow)}\\ \qquad\text{else } b_i=0; d=d/c_i \quad\text{(digit overflowed - reset and look at next digit)}\\ \quad\text{end for}\\ \quad\text{if }d=1\text{ then exit do loop} \quad\text{(all digits overflowed - done)}\\ \text{end do}\\ $