How many positive integers less than 1000 have an odd number of positive integer divisors?
Well I know that the number has to be composite because a prime number has 2 divisors, which are 1 and itself. I don't have any other thoughts to solve this problem other than brute force, which will take a long time and is not accurate. Any help? Thanks.
Best Answer
The answer is number of perfect squares less than equal to the given number, as we know perfect squares have odd number of divisors. Number of divisors of any number can be calculated by decomposing it into prime factors. If $n=p_1^{e_1}p_2^{e_2}\ldots p_n^{e_n}$ then number of divisors is $(e_1+1)(e_2+1)\ldots(e_n+1)$. Let $n = a^2$, then if $d$ is a factor then so is $\frac{n}{d}$. Thus we see that the factors are in pairs except for a because $\frac{n}{a} = a$. Thus total number of factors is $2x+1$ where $x$ is number of factors less than $a$. So odd number of factors.