C/C++プログラムで数値の階乗に含まれる末尾のゼロの個数を求める方法

本記事では、任意の整数 n の階乗（n!）の結果に含まれる「末尾のゼロ」の個数を効率的に計算する方法を解説します。

例えば、n = 5 の場合、5! = 120 となるため、末尾のゼロは 1 個です。また、20! = 2432902008176640000 の場合、末尾のゼロは 4 個になります。

素朴なアプローチとその問題点

最も単純な方法は、実際に階乗を計算してから末尾のゼロを数えることです。しかし、この方法では n が大きくなると階乗の値が急激に巨大化し、オーバーフローしてしまうため実用性がありません。

そこで、数学的な性質を利用した別のアプローチを採用します。階乗の結果に末尾のゼロが現れるのは、素因数分解した際に 2 と 5 がペアになって掛け合わされる（2 × 5 = 10）ためです。つまり、素因数の中に含まれる 2 の個数と 5 の個数を数えれば、末尾のゼロの個数が分かります。

一般的に、階乗の素因数には 5 よりも 2 の方が多く含まれるため、5 の個数だけを数えれば十分です。これを式で表すと以下のようになります。

末尾のゼロの個数 = 階乗(n) の素因数に含まれる 5 の個数

具体的には、n を 5 で割った商、25 で割った商、125 で割った商……をすべて足し合わせることで、5 の総個数を求められます。これはルジャンドルの公式として知られています。

アルゴリズム

countTrailingZeros(n)

begin
    count := 0
    for i := 5, (n/i) >= 1, increase i := i * 5, do
        count := count + (n / i)
    done
    return count;
end

C++での実装例

#include <iostream>
#include <cmath>
#define MAX 20
using namespace std;
int countTrailingZeros(int n) {
    int count = 0;
    for (int i = 5; n / i >= 1; i *= 5)
        count += n / i;
    return count;
}
main() {
    int n = 20;
    cout << "Number of trailing zeros: " << countTrailingZeros(n);
}

出力結果

Number of trailing zeros: 4

このプログラムでは、変数 i を 5 ずつではなく 5 倍ずつ増加させることで、n / 5 + n / 25 + n / 125 + ... の計算を効率的に行っています。計算量は O(log₅ n) となり、非常に大きな n に対しても高速に動作します。