Given a number $$$n$$$ find the number of its divisors not greater than given $$$k$$$ ($$$n$$$ can be even up to $$$9 * 10^{18}$$$).
This problem can be solved using some fast factorization algorithm (e.g. Pollard's rho) and then just generating every divisor not greater than $$$k$$$ (there are max $$$(9*10^{18})^{\frac{1}{3}} \approx 10^6$$$ divisors so it should be fast enough).
But, can it be done faster? (especially without iterating divisors?)
Also, is there some nice upper bound for the answer (except for the trivial number of divisors of highly composite numbers)?
This can be interpreted as a modification of subset-sum, but instead of choosing $$$0$$$ or $$$1$$$ of each number we choose from $$$0$$$ to $$$e_k$$$ of each prime. We can then prune clearly impossible cases (i.e. The product already exceeds $$$k$$$ even if we choose $$$0$$$ for the rest). Asymptotically though, I think this should still have the same time complexity.