Skip to content

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 kx.

Prime k

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

n!=123(n1)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 nk.

Next, every k2-th element is divisible by k2, 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 nk2.

And so on, for every i each ki-th element adds another +1 to the answer, and there are nki such elements.

The final answer is

nk+nk2++nki+

This result is also known as Legendre's formula. The sum is of course finite, since only approximately the first logkn elements are not zeros. Thus, the runtime of this algorithm is O(logkn).

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=k1p1kmpm. For each ki, we find the number of times it is present in n! using the algorithm described above - let's call this value ai. The answer for composite k will be

mini=1maipi