How to find maximum $x$ that $k^x$ divides $n!$

Given numbers $k$ and $n$ how can I find the maximum $x$ where: $n! \equiv\ 0 \pmod{k^x}$?

I tried to compute $n!$ and then make binary search over some range $[0,1000]$ for example compute $k^{500}$ if $n!$ mod $k^{500}$ is greater than $0$ then I compute $k^{250}$ and so on but I have to compute every time value $n!$ (storing it in bigint and everytime manipulate with it is a little ridiculous) And time to compute $n!$ is $O(n)$, so very bad. Is there any faster, math solution to this problem? Math friends?:) Cheers Chris

Solution 1:

For a prime $p$, the highest power of $p$ that divides $n!$ is $$f(n,p) = \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \left\lfloor \frac{n}{p^3} \right\rfloor + \dots.$$

So if $k$ is prime, you have the answer. (You can plug in $k$ into the above formula in place of $p$.)

Else, let the prime factorisation of $k$ be $k = p_1^{e_1}p_2^{e_2}\dots p_r^{e_r}$. Then, the highest power of $p_i^{e_i}$ dividing $n!$ is $\displaystyle\left\lfloor\frac{f(n,p_i)}{e_i}\right\rfloor$. The minimum of this expression over all $i$ gives the answer for $k$.

Solution 2:

Here is a possible approach. If $p$ is prime, the largest value of $p$ dividing $n!$ is $$\sum_{k=1}^\infty \left\lfloor {n\over p^k}\right\rfloor.$$ If the number $k$ you are considering is easily factorable into primes, you can adapt this result to your needs.

Solution 3:

Computing $n!$ it is a very bad idea for great numbers $n$. To find the desired exponent you should develop something similar to the Legendre formula.

You could also search for Legendre in the following document.