Written by Colin+ in ask uncle colin, factorising.
Dear Uncle Colin,
If you know all of the factors of $n$, can you use that to find all of the factors of $n^2$? For example, I know that 6 has factors 1, 2, 3 and 6. Its square, 36, has the same factors, as well as 4, 9, 12, 18 and 36, but I don't see an easy way to find them all -- just squaring the original factors misses 12 and 18, and looping over all of the possibilities seems inefficient, especially for larger numbers.
- Something Quite Upsetting About Recursively Enumerating Divisors
Hi, SQUARED - and thank you for your message!
Sadly, I don't think there's a quick and simple way to use the factors directly, other than (as you say) looping through them and checking.
However, there is a method to get them all from the prime factorisation of $n$. In your example, $n=2\times3$, so $n^2=2^2\times3^2$. You can list all of the factors of $36$ by listing every number of the form $2^i 3^j$, with $0\le i\le 2$ and $0\le j\le2$.
Here, you'd get:
$i=0$ | $i=1$ | $i=2$ | |
---|---|---|---|
$j=0$ | 1 | 2 | 4 |
$j=1$ | 3 | 6 | 12 |
$j=2$ | 9 | 18 | 36 |
... which all drops out nicely.
In general, if $n = p_1^{f_1}p_2^{f_2}p_3^{f_3}...p_k^{f_k}$, then $n^2$ has all possible factors of the form $p_1^{i_1}p_2^{i_2}p_3^{i_3}...p_k^{i_k}$, where $0\le i_m\le f_m$ for all $m=1,2,...,k$. In all, you'll have $(f_1+1)(f_2+1)...(f_k+1)$ factors.
Hope that helps!
- Uncle Colin