# Total number of divisors is a prime

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?

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.

• Almost right? Does that mean other numbers may have prime number of divisors? – kintoki 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 mistake...my bad – kintoki 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.

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

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.

• I just want to be sure I got it right, tired of WAs. – kintoki 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 – PleaseHelp Nov 4 '13 at 11:58
• well good luck :D i've to find the bug now :( – kintoki Nov 4 '13 at 12:01
• yup. good luck :D – PleaseHelp Nov 4 '13 at 12:02