Factors of non-square

Question

How do you solve to find how many of the positive factors of a number, say 36,000,000, are not perfect square? I know how to do this manually, which took me forever, but I want to be able to solve this more quickly and efficiently.

Answer 1

Note that $$36,000,000 = 36 \times 10^6 = 2^2 \times 3^2 \times 2^6 \times 5^6 = 2^8 \times 3^2 \times 5^{6}$$ Any square factor of the above number is of the form $4^{\alpha} 9^{\beta} 25^{\gamma}$ where $\alpha \in \{0,1,2,3,4\}$, $\beta \in \{0,1\}$ and $\gamma \in \{0,1,2,3\}$. Can you now count the number of square factors and subtract from the total number of factors?

Move your mouse for a complete answer.

The number of square factors is $5 \times 2 \times 4 = 40$, while the total number of factors is $9 \times 3 \times 7 = 189$. In general, if $n=p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$, the total number of factors is $$f_1=(1+a_1)(1+a_2)\cdots(1+a_k),$$ while the total number of square factors is $$f_2 = (1+\lfloor a_1/2 \rfloor)(1+\lfloor a_2/2 \rfloor)\cdots(1+\lfloor a_k/2 \rfloor)$$ Hence, the number of non-square factors is $f_1-f_2$.