[Math] Number of Divisors of N factorial

factorialnumber theoryprime factorization

Say $d(N) =$ Number of factors of $N!$

Briefly: I wish to know if there is a Recurrence relation for this problem.

Now I wish to Know if there is a way to calculate $d(N)$ in terms of previously calculated values …

I want to know this as a part of the problem on spoj (http://www.spoj.com/problems/EASYFACT/)

What I mentioned was a part of my approach to solve this.

Best Answer

If you know three things, namely factorisation of $N=\prod_n p_n^{i_n}$,

value of $d(N-1)$

and $m_n$ maximal power of $p_n$ dividing $(N-1)!$ for each $n$ then I think you should be able to calculate $d(N)$.

In that case $(d(N)=d(N-1)/(\prod_n(m_n+1)) \times (\prod_n(m_n+i_n+1)) $ by standard number of divisors formula.

I don't think you can simplfy much more unless I misunderstood your question.

Related Question