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
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 '13 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$ – Carlos Eugenio Thompson Pinzón Nov 4 '13 at 11:56
  • $\begingroup$ Sorry, notational mistake...my bad $\endgroup$ – kintoki Nov 4 '13 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 '13 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 '13 at 11:58
  • $\begingroup$ well good luck :D i've to find the bug now :( $\endgroup$ – kintoki Nov 4 '13 at 12:01
  • $\begingroup$ yup. good luck :D $\endgroup$ – PleaseHelp Nov 4 '13 at 12:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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