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
 A: 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$.
A: 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.
A: 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.
A: A little terminology: The highest power of a prime $p$ that can divide some number $m$ is called the multiplicity (or less memorably the $p$-adic order) of $p$ in $m$, denoted $\nu_p(m)$.
For a general $k$ you would need to consider the prime factors of $k$ in turn and find which $\dfrac{\nu_{p_i}(m)}{\nu_{p_i}(k)}$ is the least.
One common question is to ask how many trailing zeroes there are on some factorial. Then $k=10$ with single prime factors $2$ and $5$.
To find $\nu_p(n!)$ is a particularly rapid evaluation. Effectively we are being asked to sum the mulitplicities of $p$ across all the values up to $n$, and of course many of these values are coprime to $p$ - in fact only $s_1:=\left\lfloor 
\dfrac{n}{p} \right\rfloor$ values make any contribution. Then $s_2:=\left\lfloor \dfrac{n}{p^2} \right\rfloor=\left\lfloor \dfrac{s_1}{p} \right\rfloor$ have a second power of $p$ involved, and $s_3:=\left\lfloor \dfrac{n}{p^3} \right\rfloor=\left\lfloor \dfrac{s_2}{p} \right\rfloor$ have a third power of $p$, etc. So the simple process here is to repeatedly divide each term by the prime concerned until the term falls to zero.
For example, $\nu_2(555!) = 277+138+69+34+17+8+4+2+1 = 550$ and  $\nu_5(555!) = 111+22+4 = 137$ so $555!$ has $137$ trailing zeroes.
