Hello everybody,

Lately I've solved a few problems that include the number of divisors of N in their complexity. Now I'm a person that loves to know exactly the complexity of his algorithms so I tried to look around the web for the values and I read from wikipedia the Divisor Function page, but I couldn't find what I'm looking for (it might've been there, I had tough time understanding most of their explanations).

So suppose **D(n)** is the number of divisors of **n**. I'm looking for a good bound on **D(n)** expressed using **n**.

Note that it is very easy to see and prove that **D(n)<2*sqrt(n)**, but I did some tests and I believe a stronger (not much stronger but still stronger) bound should exist. Sorry if the answer is already described somewhere online, I had tough time finding it.

Thanks in advance!

I've posted a link about the topic. Basically, what I took from this article and my previous experience is that the bounds for D(N) are usually useless in programming contests because the constants involved are really unclear. I usually make do with the fact that on average N has log(N) divisors and memorizing D(N) for a few landmark highly-composite numbers such as:

A number less than 10 ^ 12 will have at most 7000 divisors, less than 10 ^ 18 up to 100000 divisors. There's actually a problem on TIMUS that I've solved and I occasionally use the code to get the maximum D(x) for some x <= N.

http://acm.timus.ru/problem.aspx?space=1&num=1748

The link I was talking about: http://terrytao.wordpress.com/2008/09/23/the-divisor-bound/

Is there an efficient solution of the above timus problem without some precalculations and hardcoding?

DP best[i][j] =

minimal number with primes up to i-th in it's factorization and exactly j divisorsfits into TL — you just have to try all possibilities for degree of next prime.Yes, there is. I do not know how exactly efficient it is, because it is recursive brute-force with obvious pruning (it is my solution, there are probably better solutions).

Yes, a smart brute force runs instantly on any test case. I think it had something like 40 000 states. Also a good number to know.

Briefly, you can use N^(1/3) for rought approximation of D(N) while solving problems. And theoretical bound is much better — D(N) is actually sub-polynomial. It is mentioned even in Wikipedia:) And this question was discussed many times in russian part of Codeforces, you may take a look at topics like this and this.

I did some tests and wow, N^(1/3) seems like a nice approximation for complexity purposes, I didn't know that. Turns out there is way stronger bound than 2*sqrt(n), and I've always thought it's not that far from that.

Thanks a lot :)

I miss a lot of useful information because I don't know Russian :( why not everybody just write in English?

Maybe because somebody does not know English?

When I need to look this up for a problem, I usually use a cheat table: http://wwwhomes.uni-bielefeld.de/achim/highly.txt. You can memorize some common bounds from there as well if you feel so inclined.

If you're looking at the number of divisors of a lot of different numbers, then you should know that it's

log(n) on average.Codeforces sending a lot of duplicate comments lately...

There has been a discussion in russian threads a few years ago: http://mirror.codeforces.com/blog/entry/651, http://mirror.codeforces.com/blog/entry/3863.