Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Which numbers have prime number of divisors?

For example, $16$ has $1$, $2$, $4$, $8$, $16$, a total of $5$ divisors, $5$ being a prime.

I found that primes and the power of primes such that $p^{q-1}$, where $p$ and $q$ are prime numbers, all have prime number of divisors. Is this property limited to only these numbers?

share|cite|improve this question
up vote 13 down vote accepted

If $n=p_1^{k_1}p_2^{k_2}\cdots p_h^{k_h}$ for ($p_i$ prime), then the number of divisors will be $(k_1+1)(k_2+1)\cdots(k_h+1)$.

So you are almost right. You need only one prime $p_1$ in the factorization and its exponent $k_1$ must be a prime minus one.

share|cite|improve this answer
Almost right? Does that mean other numbers may have prime number of divisors? – akki Nov 4 '13 at 11:54
It means that it does not need to be $p^{p-1}$ but it can be $p^{q-1}$ where $p,q$ are different primes. Of course, given your example of $16=2^{5-1}$ it might be a notational problem. – Carlos Eugenio Thompson Pinzón Nov 4 '13 at 11:56
Sorry, notational bad – akki Nov 4 '13 at 11:59

If $n$ has at least two different prime divisors, $n=ab$ with $\gcd(a,b)=1$, $a,b>1$, then $\tau(n)=\tau(a)\tau(b)$ is not prime (because $\tau(a),\tau(b)>1$). If $n$ is a power of a prime, $n=p^k$, then Indeed, $\tau(p^k)=k+1$ and this is prime iff $k+1$ is prime. Thus exactly the numbers of the form $n=p^{q-1}$ where $p,q$ re prime have the desired property.

share|cite|improve this answer

Can you prove that if $n=p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$ then the number of divisors of $n$ is given by $(a_1+1)(a_2+1)\cdots (a_k+1).$ For this to be prime, you are forced to have $n=p^a$ i.e. $n$ is a power of a prime. Then $n$ has a prime number of divisors as long as $a$ is one less than any prime number (not just $p$).

share|cite|improve this answer

If the number is a prime or is of the form $p^{q-1}$ where both p and q are prime, then and then only the Number will have prime number of Divisors.

NOTE :- I know this is a current codechef problem. Even after knowing this you may still experience TLE.

share|cite|improve this answer
I just want to be sure I got it right, tired of WAs. – akki Nov 4 '13 at 11:57
and i m tired of TLE's :P. But it seems that i just found the right optimisation :D – atulgangwar Nov 4 '13 at 11:58
well good luck :D i've to find the bug now :( – akki Nov 4 '13 at 12:01
yup. good luck :D – atulgangwar Nov 4 '13 at 12:02

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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