You are given two numbers <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>n</mi></math>$n$ and <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>k</mi></math>$k$. Find the largest power of <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>k</mi></math>$k$<math xmlns="http://www.w3.org/1998/Math/MathML"><mi>x</mi></math>$x$ such that <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>n</mi><mo>!</mo></math>$n!$ is divisible by <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mi>k</mi><mi>x</mi></msup></math>$k^x$.
Prime <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>k</mi></math>$k$¶
Let's first consider the case of prime <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>k</mi></math>$k$. The explicit expression for factorial
Note that every <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>k</mi></math>$k$-th element of the product is divisible by <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>k</mi></math>$k$, i.e. adds <math xmlns="http://www.w3.org/1998/Math/MathML"><mo>+</mo><mn>1</mn></math>$+1$ to the answer; the number of such elements is <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow data-mjx-texclass="OPEN"><mo minsize="1.623em" maxsize="1.623em">⌊</mo></mrow><mstyle displaystyle="true" scriptlevel="0"><mfrac><mi>n</mi><mi>k</mi></mfrac></mstyle><mrow data-mjx-texclass="CLOSE"><mo minsize="1.623em" maxsize="1.623em">⌋</mo></mrow></math>$\Bigl\lfloor\dfrac{n}{k}\Bigr\rfloor$.
Next, every <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mi>k</mi><mn>2</mn></msup></math>$k^2$-th element is divisible by <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mi>k</mi><mn>2</mn></msup></math>$k^2$, i.e. adds another <math xmlns="http://www.w3.org/1998/Math/MathML"><mo>+</mo><mn>1</mn></math>$+1$ to the answer (the first power of <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>k</mi></math>$k$ has already been counted in the previous paragraph). The number of such elements is <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow data-mjx-texclass="OPEN"><mo minsize="1.623em" maxsize="1.623em">⌊</mo></mrow><mstyle displaystyle="true" scriptlevel="0"><mfrac><mi>n</mi><msup><mi>k</mi><mn>2</mn></msup></mfrac></mstyle><mrow data-mjx-texclass="CLOSE"><mo minsize="1.623em" maxsize="1.623em">⌋</mo></mrow></math>$\Bigl\lfloor\dfrac{n}{k^2}\Bigr\rfloor$.
And so on, for every <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>i</mi></math>$i$ each <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mi>k</mi><mi>i</mi></msup></math>$k^i$-th element adds another <math xmlns="http://www.w3.org/1998/Math/MathML"><mo>+</mo><mn>1</mn></math>$+1$ to the answer, and there are <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow data-mjx-texclass="OPEN"><mo minsize="1.623em" maxsize="1.623em">⌊</mo></mrow><mstyle displaystyle="true" scriptlevel="0"><mfrac><mi>n</mi><msup><mi>k</mi><mi>i</mi></msup></mfrac></mstyle><mrow data-mjx-texclass="CLOSE"><mo minsize="1.623em" maxsize="1.623em">⌋</mo></mrow></math>$\Bigl\lfloor\dfrac{n}{k^i}\Bigr\rfloor$ such elements.
This result is also known as Legendre's formula.
The sum is of course finite, since only approximately the first <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>log</mi><mi>k</mi></msub><mo data-mjx-texclass="NONE"></mo><mi>n</mi></math>$\log_k n$ elements are not zeros. Thus, the runtime of this algorithm is <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>O</mi><mo stretchy="false">(</mo><msub><mi>log</mi><mi>k</mi></msub><mo data-mjx-texclass="NONE"></mo><mi>n</mi><mo stretchy="false">)</mo></math>$O(\log_k n)$.
The same idea can't be applied directly. Instead we can factor <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>k</mi></math>$k$, representing it as <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>k</mi><mo>=</mo><msubsup><mi>k</mi><mn>1</mn><mrow data-mjx-texclass="ORD"><msub><mi>p</mi><mn>1</mn></msub></mrow></msubsup><mo>⋅</mo><mo>…</mo><mo>⋅</mo><msubsup><mi>k</mi><mi>m</mi><mrow data-mjx-texclass="ORD"><msub><mi>p</mi><mi>m</mi></msub></mrow></msubsup></math>$k = k_1^{p_1} \cdot \ldots \cdot k_m^{p_m}$. For each <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>k</mi><mi>i</mi></msub></math>$k_i$, we find the number of times it is present in <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>n</mi><mo>!</mo></math>$n!$ using the algorithm described above - let's call this value <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>a</mi><mi>i</mi></msub></math>$a_i$. The answer for composite <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>k</mi></math>$k$ will be