How many divisors of $n$ are less than or equal to $m$?

Question

Can I calc it in less than $O(\sqrt{n})$ time?

Answer 1

The algorithm:

1. Factorize $n$ using any sub-exponential (in term of the binary length of $n$) algorithm, e.g. General number field sieve.
2. According to asymptotics of the Divisor function, the number of divisors of $n$ is sub-exponential. So just run through the list of all its divisors and compare with $m$.

Since both steps take sub-exponential time, the overall run time will be sub-exponential, and thus in $o(\sqrt{n})$ (little-o notation).