Given two numbers $$n$$ and $$k$$ find the greatest power of $$k$$ that divides $$n!$$

Writing the factorial expression explicitely

$n! = 1 \cdot 2 \cdot 3 \ldots (n - 1) \cdot n$

We can see that every $$k$$-th member of the factorial is divisible by $$k$$ therefore one answer is $$\left \lfloor \tfrac{n}{k} \right \rfloor$$, however we can also see that every $$k^2$$-th term is also divisible by $$k$$ two times and it gives one more term to the answer, that is $$\left \lfloor \tfrac{n}{k^2} \right \rfloor$$, which means that every $$k^i$$-th term adds one factor to the answer, thus the answer is

$\left \lfloor \frac{n}{k} \right \rfloor + \left \lfloor \frac{n}{k^2} \right \rfloor + \ldots + \left \lfloor \frac{n}{k^i} \right \rfloor + \ldots$

The sum is actually finite and the maximum value of $$i$$ can be found using logarithms, let $$k^i > n$$, applying logarithms we have $$i \cdot log(k) > log(n)$$ which is equal to $$i > \tfrac{log(n)}{log(k)}$$ which is the same as $$i > log_k n$$

The sum discovered by Adrien-Marie Legendre is called Legendre's Formula, let $$d_a(b)$$ be the number of times $$a$$ divides $$b$$

$d_k(n!) = \sum_{i=1}^{log_k{n}} \left \lfloor \frac{n}{k^i} \right \rfloor$

/**
* Computes the maximum power of k that is a divisor of n!
*
* @param {int} n
* @param {int} k
* @return {int}
*/
int max_power_in_factorial(int n, int k) {
int ans = 0;
while (n) {
n /= k;
ans += n;
}
return ans;
}