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;
}