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

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!

• Does $2^3$ really divide $420$? – Lord Shark the Unknown May 15 '18 at 18:21
• Whoops, that's supposed to be a $2^2$ thanks for pointing that out. – Alex May 15 '18 at 18:22
• Don't you mean $\displaystyle \prod_{i=1}^r (a_r+1)$ ? I also got 32 possible factors by $4(2)(2)(2)$. it's 30 if you get rid of the trivial ones – N8tron May 15 '18 at 18:23
• It's not 32, I just put the wrong power for 2, it's definitely 24. Sorry! – Alex May 15 '18 at 18:25

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}

• Wow! This was exactly what I was looking for, that's so cool! – Alex May 15 '18 at 20:12
• Or we can put the table in n-dimensional space, where n is the number of distinct prime factors. – Acccumulation May 15 '18 at 22:18
• @Acccumulation I couldn't get the 4-dimensional formatting to work :-) – Joffan May 15 '18 at 22:46
• @Joffan You can simulate the 4D formatting by using a 2D table of 2D tables, like \begin{array}{ccccc|ccc} & & & 1 & & & 5\\ & & & & \\ 1 & & 1 & 2 & 4 & 5 & 10 & 20\\ & & 3 & 6 & 12 & 15 & 30 & 60\\ \hline 7 & & 7 & 14 & 28 & 35 & 70 & 140\\ & & 21 & 42 & 84 & 105 & 210 & 420 \end{array} – Mark S. May 16 '18 at 2:06
• hmmm... I personally prefer the "odometer" reading. Factor is $n = 2^a3^b5^c7^d$ so just list out all the $(d,c,b,a)$ as they roll out on an odometer. $(0,0,0,0)$ $(0,0,0,1)$, $(0,0,0,2)$, $(0,0,1,0)$, $(0,0,1,1)$,$(0,0,1,2)$, $(0,1,0,0)$, etc.... so $(1,0,1, 2)$ for instance would be $7^1*5^0*3^1*2^2 = 7*3*4 = 84$. That way I wouldn't need my 4-dimensional table formating. – fleablood May 16 '18 at 15:22

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

• So out of those 84 only 24 of them are unqiue? Is this really the simplest way of finding all the factors? That's so much distributing and elinimating duplicates. – Alex May 15 '18 at 18:28
• $84$ is one of the $24$ divisors. All $24$ divisors are unique. – vadim123 May 15 '18 at 18:29
• Oh I get it! That's really cool :) – Alex May 15 '18 at 18:30

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

• Notice that the exponents form a mixed radix number that is repeatedly incremented (by $1$) with radices (left-to-right) 3, 2, 2, 2. It's a little weird to increment on the left and carry to the right, but that could be fixed in several ways. – Eric Towers May 16 '18 at 3:19
• In an earlier edit I first listed from right to left (first the 7, then the 5, and the twos last). But I think going from left to right seemed more natural as we are doing the generally smaller terms first. Also I prefer "rolling " through the terms with the highest powers first. But frankly I really don't think it matters. Does it? – fleablood May 16 '18 at 4:32
• The increment is easier to pick out of the visual noise (all the non-superscripts) if it is $0000, 0001, 0002, 0010, \dots$. It's not necessary, but it may well be clearer. – Eric Towers May 16 '18 at 6:16
• I was hoping that would be clear. But without the "visual noise" I don't know if someone would see or understand that 0000=1,0001=2,0002=4,0010=3 etc. – fleablood May 16 '18 at 15:14

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}\\$