You are given two numbers \(n\) and \(k\). Find the largest power of \(k\) \(x\) such that \(n!\) is divisible by \(k^x\).
Let's first consider the case of prime \(k\). The explicit expression for factorial
\[ n! = 1 \cdot 2 \cdot 3 \ldots (n-1) \cdot n \]Note that every \(k\)-th element of the product is divisible by \(k\), i.e. adds \(+1\) to the answer; the number of such elements is \(\Bigl\lfloor\dfrac{n}{k}\Bigr\rfloor\).
Next, every \(k^2\)-th element is divisible by \(k^2\), i.e. adds another \(+1\) to the answer (the first power of \(k\) has already been counted in the previous paragraph). The number of such elements is \(\Bigl\lfloor\dfrac{n}{k^2}\Bigr\rfloor\).
And so on, for every \(i\) each \(k^i\)-th element adds another \(+1\) to the answer, and there are \(\Bigl\lfloor\dfrac{n}{k^i}\Bigr\rfloor\) such elements.
The final answer is
\[ \Bigl\lfloor\dfrac{n}{k}\Bigr\rfloor + \Bigl\lfloor\dfrac{n}{k^2}\Bigr\rfloor + \ldots + \Bigl\lfloor\dfrac{n}{k^i}\Bigr\rfloor + \ldots \]The sum is of course finite, since only approximately the first \(\log_k n\) elements are not zeros. Thus, the runtime of this algorithm is \(O(\log_k n)\).
int fact_pow (int n, int k) {
int res = 0;
while (n) {
n /= k;
res += n;
}
return res;
}
The same idea can't be applied directly. Instead we can factor \(k\), representing it as \(k = k_1^{p_1} \cdot \ldots \cdot k_m^{p_m}\). For each \(k_i\), we find the number of times it is present in \(n!\) using the algorithm described above - let's call this value \(a_i\). The answer for composite \(k\) will be
\[ \min_ {i=1 \ldots m} \dfrac{a_i}{p_i} \]