Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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^{p-1}$, where $p$ is any prime number, all have prime number of divisors. Is this property limited to only these numbers?

share|improve this question

4 Answers 4

up vote 12 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|improve this answer
    
Almost right? Does that mean other numbers may have prime number of divisors? –  akki Nov 4 '13 at 11:54
1  
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 –  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|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|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|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 –  Atul Gangwar 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 –  Atul Gangwar Nov 4 '13 at 12:02

Your Answer

 
discard

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.