【C++】階乗の末尾に並ぶゼロの個数を効率的に求める方法

整数を入力として与え、その数の階乗における末尾のゼロ（後続ゼロ）の個数を求めるのが本記事の目的です。ここで、ある数 N の階乗とは、1 から N までのすべての整数の積を指します。

末尾のゼロが生まれる仕組み

数の末尾にゼロが付くのは、その数が 10 の倍数である場合、すなわち因数として (2, 5) のペアを持つ場合だけです。5 より大きい任意の数の階乗を素因数分解すると、2 の個数は必ず 5 の個数よりも多くなるという性質があります。

そこで、対象の数を 5 の累乗で順に割っていくことで、因数に含まれる 5 の総数を求められます。この「5 の個数」がそのまま末尾のゼロの個数と一致するのです。

入出力例

例1

入力：

number=6

出力：

Count of trailing zeros in factorial of a number are: 1

解説：

6 の階乗は 30。
30 の素因数分解：2 * 3 * 5
(2, 5) のペアは 1 組しか存在しないため、末尾のゼロは 1 個。

例2

入力：

number=12

出力：

Count of trailing zeros in factorial of a number are: 2

解説：

12 の階乗は 479001600。
素因数分解：2^10 × 3^5 × 5^2 × 7^1 × 11^1
(2, 5) のペアが 2 組得られるため、末尾のゼロは 2 個。

アルゴリズムの考え方

本プログラムでは、次の方針で計算を行います。対象の数を 5 の累乗（5, 25, 125, …）で順番に割り、商が 1 以上である限りその商をカウントに加算していきます。こうして集計された値こそが、階乗に含まれる 5 の個数、すなわち末尾のゼロの個数となります。

• 整数を入力として受け取ります。
• 関数 trailing_zeros(int number) が数を受け取り、その階乗における末尾のゼロの個数を返します。
• カウントの初期値を 0 に設定します。
• for ループを用いて、数を 5 の累乗で順に割っていきます。
• number / i が 1 以上であれば、その値をカウントに加算します。
• ループ終了後、カウントを結果として返します。

C++ サンプルコード

#include <iostream>
using namespace std;
int trailing_zeros(int number){
    int count = 0;
    for (int i = 5; number / i >= 1; i *= 5){
        int temp = number / i;
        count = count + temp;
    }
    return count;
}
int main(){
    int number = 50;
    cout<<"Count of trailing zeros in factorial of a number are: "<<trailing_zeros(number);
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

Count of trailing zeros in factorial of a number are: 12

50 の階乗には 5 が 12 個（5 の倍数から 10 個、25 の倍数からさらに 2 個）含まれるため、末尾のゼロは 12 個となります。この方法を使えば、巨大な階乗を実際に計算することなく、O(log N) の計算量で末尾のゼロの個数を瞬時に求められます。