18
$\begingroup$

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?

$\endgroup$
0

4 Answers 4

14
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Almost right? Does that mean other numbers may have prime number of divisors? $\endgroup$
    – kintoki
    Nov 4, 2013 at 11:54
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 4, 2013 at 11:56
  • $\begingroup$ Sorry, notational mistake...my bad $\endgroup$
    – kintoki
    Nov 4, 2013 at 11:59
5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ I just want to be sure I got it right, tired of WAs. $\endgroup$
    – kintoki
    Nov 4, 2013 at 11:57
  • $\begingroup$ and i m tired of TLE's :P. But it seems that i just found the right optimisation :D $\endgroup$
    – PleaseHelp
    Nov 4, 2013 at 11:58
  • $\begingroup$ well good luck :D i've to find the bug now :( $\endgroup$
    – kintoki
    Nov 4, 2013 at 12:01
  • $\begingroup$ yup. good luck :D $\endgroup$
    – PleaseHelp
    Nov 4, 2013 at 12:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .