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

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

-
Is $n \gt m^2$? –  Henry Jul 9 '13 at 11:26
What do you mean by less than $O(\sqrt{n})$? The latter expression already has a meaning of upper bound. –  ftfish Jul 9 '13 at 11:32
@ftfish I hope for a algorithm has a better bound. –  Tang Xianghao Jul 9 '13 at 12:14
@Henry It's not necessary. –  Tang Xianghao Jul 9 '13 at 12:18
@TangXianghao: If $m=2$ and $n$ is large then you can do the calculation rather faster than $O(\sqrt{n})$ –  Henry Jul 9 '13 at 13:22
show 1 more comment

1 Answer

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).

-
add comment