Last update: January 27, 2023  Translated From: e-maxx.ru

Finding Power of Factorial Divisor

You are given two numbers   $n$  and   $k$ . Find the largest power of   $k$    $x$  such that   $n!$  is divisible by   $k^x$ .

Prime   $k$ 

Let's first consider the case of prime   $k$ . The explicit expression for factorial

  $$n!=1\cdot 2\cdot 3\dots (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   $\lfloor {\displaystyle \frac{n}{k}}\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   $\lfloor {\displaystyle \frac{n}{k^2}}\rfloor$ .

And so on, for every   $i$  each   $k^i$ -th element adds another   $+1$  to the answer, and there are   $\lfloor {\displaystyle \frac{n}{k^i}}\rfloor$  such elements.

The final answer is

  $$\lfloor {\displaystyle \frac{n}{k}}\rfloor +\lfloor {\displaystyle \frac{n}{k^2}}\rfloor +\dots +\lfloor {\displaystyle \frac{n}{k^i}}\rfloor +\dots$$ 

This result is also known as Legendre's formula. 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)$ .

Implementation

int fact_pow (int n, int k) {
    int res = 0;
    while (n) {
        n /= k;
        res += n;
    }
    return res;
}

Composite   $k$ 

The same idea can't be applied directly. Instead we can factor   $k$ , representing it as   $k=k_1^{p_1}\cdot \dots \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

  $$\underset{i=1\dots m}{min}{\displaystyle \frac{a_i}{p_i}}$$ 

Contributors:
• adamant-pwn (65.31%)
• tcNickolas (28.57%)
• KunalSin9h (4.08%)
• jxu (2.04%)