C 語言計算 n! 末尾零的個數：計算質因子 5 的指數

數學原理

末尾零來源於 10 = 2 × 5。階乘中因子 2 遠多於 5，**零的個數 = n! 中質因子 5 的總指數**。

每 5 貢獻 1 個 5，每 25 貢獻額外 1 個，每 125 再額外 1 個……

公式：count = n/5 + n/25 + n/125 + ... (直到商為 0)

C 代碼

#include <stdio.h>

int trailingZeros(int n) {
    int count = 0;
    for (int i = 5; i <= n; i *= 5)
        count += n / i;
    return count;
}

int main() {
    int n;
    while (scanf("%d", &n) == 1)
        printf("%d\n", trailingZeros(n));
    return 0;
}

測試

複雜度

時間 O(log₅ n)，空間 O(1)，極高效。