C/C++プログラミング：階乗の末尾に連続するゼロの個数を数える方法

階乗の値の末尾に連続するゼロ（後続ゼロ）の個数を求めるには、その数の因数に含まれる「2」と「5」の個数を数えます。これは、2×5＝10という組み合わせが、階乗の末尾にゼロを1つ生み出すためです。

例：7の階乗の場合

7の階乗（7!）は5040であり、末尾のゼロは1個です。

ロジックに基づいて確認してみましょう。7! = 2×3×4×5×6×7 であり、因数のうち2は3個、5は1個含まれています。ペアにできる2と5の組み合わせは1組だけなので、末尾のゼロの個数は1個となります。

効率的なアルゴリズム：5の個数だけを数える

階乗の因数において、2の個数は必ず5の個数以上になります。そのため、実際には5の個数だけを数えれば末尾のゼロの個数が求まります。

以下のプログラムでは、nを5で順に割っていくことで、5の倍数・25の倍数・125の倍数…に含まれる5の個数を効率的に合計しています。

#include <iostream>
using namespace std;
int main() {
   int n = 45;
   int count = 0;
   for (int i = 5; n / i >= 1; i *= 5)
      count += n / i;
   cout<<"No of trailing 0s in " << n<< "! is " << count;
   return 0;
}

出力結果

No of trailing 0s in 45! is 10

計算の流れを確認

n = 45の場合、プログラムは次のように動作します。

• 45 ÷ 5 = 9 → 5の倍数が9個（5, 10, 15, 20, 25, 30, 35, 40, 45）
• 45 ÷ 25 = 1 → 25の倍数が1個（25は5を2つ含むため、さらに1加算）
• 45 ÷ 125 = 0 → ループ終了

合計 9 + 1 = 10 となり、45! の末尾のゼロは10個であることがわかります。このアルゴリズムの計算量はO(log n)と非常に効率的で、大きな数の階乗でも高速に末尾ゼロの個数を求められます。