Counting an integer's divisors without just enumerating them (or estimating if not possible)?
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)$.