經典演算法題：1000 階乘末尾有幾個 0？數學解法與 Java 實作

題目

計算 1000!（1000 階乘）的十進位表示中，末尾連續有多少個 0？

數學原理

十進位下，末尾的 0 來源於因子 10 = 2 × 5。在階乘展開式中：

1000! = 1 × 2 × 3 × 4 × 5 × ... × 999 × 1000

因子 2 的數量遠多於因子 5（每隔 2 個數有一個 2，每隔 5 個數才有一個 5），所以 0 的個數 = 因子 5 的總個數。

計算因子 5 個數

每個 5 的倍數貢獻至少 1 個 5；25 的倍數額外貢獻 1 個（25 = 5²）；125 的倍數再額外 1 個（125 = 5³）；625 的倍數再額外 1 個（625 = 5⁴）。

公式：

count = ⌊1000/5⌋ + ⌊1000/25⌋ + ⌊1000/125⌋ + ⌊1000/625⌋ + ...
      = 200 + 40 + 8 + 1 = 249

Java 實作：兩種解法對比

解法一：暴力模擬（教學用，不可用於大數）

原始碼逐一分解 1~1000 每個數的因子 2、5，累加計數。時間複雜度 O(N log N)，N=1000 尚可接受，但 N=10⁷ 會超時。

public class FactorialTrailingZerosBruteForce {
    public static void main(String[] args) {
        int count2 = 0, count5 = 0;
        for (int n = 1; n <= 1000; n++) {
            int x = n;
            while (x % 2 == 0) { count2++; x /= 2; }
            while (x % 5 == 0) { count5++; x /= 5; }
        }
        System.out.println("末尾 0 的個數：" + Math.min(count2, count5)); // 249
    }
}

解法二：數學公式 O(log₅N)（生產環境標準解）

public class FactorialTrailingZeros {
    /**
     * 計算 n! 末尾 0 的個數
     * @param n 非負整數
     * @return 末尾連續 0 的數量
     */
    public static long trailingZeros(long n) {
        long count = 0;
        for (long divisor = 5; divisor <= n; divisor *= 5) {
            count += n / divisor;
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println("1000! 末尾 0 的個數：" + trailingZeros(1000)); // 249
        System.out.println("10000! 末尾 0 的個數：" + trailingZeros(10000)); // 2499
        System.out.println("100000! 末尾 0 的個數：" + trailingZeros(100000)); // 24999
    }
}

進階延伸：任意進位制下的尾隨 0

若題目改為「1000! 在 16 進位（Hex）下末尾有幾個 0？」，原理相同：

• 16 = 2⁴，只需計算因子 2 的總個數，再除以 4 取整
• 通用公式：對進位制 B 做質因數分解 B = p₁^e₁ × p₂^e₂ × ...，尾隨 0 數 = min( count(pᵢ) / eᵢ )

public static long trailingZerosInBase(long n, int base) {
    // 質因數分解 base
    Map factors = new HashMap<>();
    int b = base;
    for (int p = 2; p * p <= b; p++) {
        while (b % p == 0) {
            factors.merge(p, 1, Integer::sum);
            b /= p;
        }
    }
    if (b > 1) factors.merge(b, 1, Integer::sum);

    long minZeros = Long.MAX_VALUE;
    for (Map.Entry entry : factors.entrySet()) {
        int prime = entry.getKey();
        int exp = entry.getValue();
        long primeCount = 0;
        for (long d = prime; d <= n; d *= prime) {
            primeCount += n / d;
        }
        minZeros = Math.min(minZeros, primeCount / exp);
    }
    return minZeros;
}

BigInteger 驗證（小數值）

為了驗證邏輯，可用 BigInteger 實際算出階乘再數 0（僅適用 N ≤ 2000 記憶體許可範圍）：

import java.math.BigInteger;

public class Verify {
    public static void main(String[] args) {
        BigInteger fact = BigInteger.ONE;
        for (int i = 2; i <= 100; i++) fact = fact.multiply(BigInteger.valueOf(i));
        String s = fact.toString();
        int zeros = 0;
        for (int i = s.length() - 1; i >= 0 && s.charAt(i) == '0'; i--) zeros++;
        System.out.println("100! 實際末尾 0 數：" + zeros); // 24
        System.out.println("公式計算：" + FactorialTrailingZeros.trailingZeros(100)); // 24
    }
}

總結

核心洞見：階乘尾隨 0 純粹是質因數 2 與 5 的博弈，只要數清 5 就夠了。這類題目考察的不是程式技巧，而是數論直覺——能否跳出「模擬運算」框架，轉向「數學結構」分析。