Find numbers with n-divisors in a given range

divisibilityprime factorizationprime numbers

I'm trying to answer this question.

Are there positive integers $\le200$ which have exactly 13 positive divisors? What about 14 divisors? If yes, write them. If no, explain why not.

Because I'm only familiar with prime factorization, the sieve of Eratosthenes etc. about this topic I need help to understand how to reasoning with this kind of questions.

Best Answer

For any number $n=p_1^{\alpha_1}p_2^{\alpha_2}p_3^{\alpha_3}\dots p_k^{\alpha_k}$ the number of divisors (including $1$ and $n$) is $d=\prod({\alpha_i +1})$. If $d=13$, since $13$ is prime, there is only one possibility: $n=p_i^{12}$. The smallest such number is $2^{12}$ which is larger than $200$, so there are no numbers satisfying this requirement. If $d=14=2\cdot 7$ candidate numbers will have the form $n=p_1\cdot p_2^6$. The smallest such number is $3\cdot 2^6 =192$ which meets your requirement of being less than $200$.

Added by edit: The formula $d=\prod({\alpha_i +1})$ is simply the $\tau (n)$ referred to in the comments. Also, just for completeness sake, the $14$ divisors of $192$ are: $1,2,4,8,16,32,64,3,6,12,24,48,96,192$.

Related Question