This question already has an answer here:

This could be a classic problem or my wording might be totally off, but I can't seem to find an answer to this problem:

Given $n\in\mathbb{Z}$ with prime factorization $n=p_1^{q_1}\dots p_m^{q_m}$, how many integers divide $n$? For the sake of this problem, let's ignore $1$ and $n$ until the end.

First off, we have that there are at least $q_1\dots q_n$ divisors, since there are $q_1$ divisors made up of $p_1$ (namely $p_1,p_1^2,\dots,p_1^{q_1}$), thus the same holds for $p_2,\dots,p_n$

I've never done much with combinatorics, so I'm not quite sure how to begin counting unique divisors by mixing and matching distinct primes. Any thoughts?


marked as duplicate by user91500, Joey Zou, naslundx, Dietrich Burde, Claude Leibovici Sep 15 '16 at 9:25

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


Let $n=p_1^{q_1}\dots p_m^{q_m}$. Then we see that the divisors of $n$ that are powers of $p_1$ will be:

$1, p_1, p_1^2, p_1^3, ..., p_1^{q_1}$

The divisors of $n$ that are powers of $p_2$ will be:

$1, p_2, p_2^2, p_2^3, ..., p_2^{q_2}$

And so on.

What we notice is that any factor of $n$ (including $1$ and $n$) can be generated by taking exactly one number from each of the prime factor power sequences and multiplying them all together. There are $q_1+1$ numbers in the $p_1$ sequence, $q_2+1$ numbers in the $p_2$ sequence, etc. Therefore, we see that there are $(q_1+1)\times...\times(q_n+1)$ factors of $n$.


Not the answer you're looking for? Browse other questions tagged or ask your own question.