Trailing Zeroes in a Factorial

Problem. How many zeros does $n!$ end with?

The answer

$10=2\times 5$, and $n!$ always contains more factors of 2 than of 5 (every second number is even, only every fifth is a multiple of 5). So the count of trailing zeros is the exponent of 5:

$Z(n)=\lfloor \frac{n}{5}\rfloor +\lfloor \frac{n}{25}\rfloor +\lfloor \frac{n}{125}\rfloor +\dots$

long long trailingZeroes(long long n) {
    long long c = 0;
    for (long long p = 5; p <= n; p *= 5) c += n / p;
    return c;
}

$O({\log }_{5}n)$. Note p *= 5 can overflow if written as n / p with p beyond n — the loop condition guards it.

Each term counts a different factor of 5: $\lfloor n/5\rfloor$ counts multiples of 5, $\lfloor n/25\rfloor$ counts the extra 5 contributed by multiples of 25, and so on.

Legendre’s formula

The general statement — the exponent of a prime $p$ in $n!$:

$v_p(n!)={\sum }_{i\ge 1}\lfloor \frac{n}{p^i}\rfloor =\frac{n-s_p(n)}{p-1},$

where $s_p(n)$ is the digit sum of $n$ in base $p$. The second form is a nice closed expression and shows immediately that $v_p(n!)\approx \frac{n}{p-1}$.

long long legendre(long long n, long long p) {
    long long e = 0;
    for (long long q = p; q <= n; q *= p) e += n / q;
    return e;
}

Trailing zeros in other bases

Factor the base $b=\prod q_i^{a_i}$; the answer is

${\min }_i\lfloor \frac{v_{q_i}(n!)}{a_i}\rfloor .$

long long trailingZeroesBase(long long n, long long b) {
    long long best = LLONG_MAX;
    for (long long q = 2; q * q <= b; q++) {
        if (b % q) continue;
        int a = 0;
        while (b % q == 0) { b /= q; a++; }
        best = min(best, legendre(n, q) / a);
    }
    if (b > 1) best = min(best, legendre(n, b));
    return best;
}

For base 12 $=2^2\cdot 3$: $\min (v_2(n!)/2,v_3(n!))$ — and here the 2s are the binding constraint, unlike base 10.

The related results

Question	Answer
Trailing zeros of $n!$	$\sum \lfloor n/5^i\rfloor$
Exponent of $p$ in $n!$	Legendre’s formula
Exponent of $p$ in $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$	$v_p(n!)-v_p(k!)-v_p((n-k)!)$
Is $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ divisible by $p$?	Kummer: iff adding $k$ and $n-k$ in base $p$ produces a carry
$\left(\genfrac{}{}{0ex}{}{n}{k}\right)\mathrm{mod}p$	Lucas
Last non-zero digit of $n!$	a periodic pattern; needs care with the removed 5s
Smallest $n$ with exactly $z$ trailing zeros	binary search $Z(n)$ — note some $z$ are unattainable

Kummer’s theorem

The exponent of $p$ in $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ equals the number of carries when adding $k$ and $n-k$ in base $p$. A surprising and genuinely useful reformulation — it makes “is this binomial coefficient odd?” a one-line bit test:

$\left(\genfrac{}{}{0ex}{}{n}{k}\right)\text{ is odd}⟺(k\&n)=k⟺k\text{’s bits are a submask of }n\text{’s}.$

The number of odd entries in row $n$ of Pascal’s triangle is therefore $2^{\mathrm{popcount}(n)}$ — the Sierpiński-triangle pattern.

Smallest $n$ with $z$ trailing zeros

$Z$ is non-decreasing but skips values (it jumps by 2 at $n=25$, by 3 at $n=125$), so not every $z$ is achievable. Binary search $Z(n)\ge z$ and verify equality:

long long smallestWithZeros(long long z) {
    long long lo = 0, hi = 5 * (z + 1);
    while (lo < hi) { long long mid = (lo + hi) / 2; if (trailingZeroes(mid) >= z) hi = mid; else lo = mid + 1; }
    return trailingZeroes(lo) == z ? lo : -1;               // unattainable
}

Why it is worth knowing

It is the smallest problem that teaches “count the prime factorisation, not the number”. Computing $n!$ and counting its zeros is impossible for $n=10^{18}$; counting the factors of 5 is four lines. That reframing — work with the exponents of primes rather than the value — is the standard approach to every divisibility question about factorials and binomials.

See also: Factorial Modulo p · Lucas Theorem · Wilson’s Theorem