Problem Detail: I’m trying to count the number of divisors an integer $n$ has. The simple way to do this is to just enumerate all integers from 1 to $sqrt{n}$, and count how many integers evenly divide $n$. For example, 28 has six divisors (1, 2, 4, 7, 14, 28). 15 has four (1, 3, 5, 15). I want to, say, figure out how many divisors 242134575355654335549798955848371716626563756785 has. I’m not trying to factor the integer; I don’t care about what two numbers or what three numbers and so on I can multiply to get $n$. How can I count (or estimate, if need be) the number of divisors an integer has other than by enumerating them? I don’t need the actual values for each divisor; I just want to count them faster than by just enumerating them. If that’s not possible, I’d be OK with estimating the number of divisors (and, even better, using that estimate to help me find the actual number of divisors).
Asked By : JesseTG
Answered By : Yuval Filmus
As far as I know we don’t know a smart method of distinguishing between numbers which have $a$ divisors and numbers which have $b$ divisors, unless (say) $a$ is prime (in which case necessarily the number is an $(a-1)$th power of a prime, and we can use root extraction and primality testing). On the other hand, if you factor $n = prod_i p_i^{d_i}$ then you can compute the number of factors using the formula $prod_i (d_i + 1)$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/49532
