【Python】数の階乗に含まれる末尾のゼロを効率的にカウントする方法

はじめに

この記事では、与えられた整数の階乗（n!）に含まれる「末尾のゼロ」の個数を求めるPythonプログラムについて解説します。

問題文

整数 n が与えられたとき、n! の末尾に連続して現れるゼロの個数を数えます。
例えば、10! = 3628800 であるため、末尾のゼロは2個です。

アプローチのポイント：なぜ「5」を数えるのか

階乗の末尾にゼロが付くのは、10 = 2 × 5 という因数の組み合わせが生まれるためです。n! の中では2の因数の方が5の因数よりも圧倒的に多く含まれるため、末尾のゼロの個数は「5の因数の総数」と一致します。

この性質を利用すると、次の式（レジャンドルの公式）で末尾のゼロの個数を求めることができます。

末尾のゼロの個数 = ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + …

実装例

# 末尾のゼロを数える関数
def find(n):
    # カウントを初期化
    count = 0
    # 5のべき乗ごとにカウントを更新
    i = 5
    while (n / i >= 1):
        count += int(n / i)
        i *= 5
    return int(count)

# ドライバープログラム
n = 79
print('Count of trailing 0s in', n, '! is', find(n))

出力

Count of trailing 0s in 79 ! is 18

コードの解説

変数 i を 5 から始めて 5 倍しながら更新し、n / i が 1 以上である間、n ÷ i の商（小数点以下切り捨て）を count に加算していきます。これにより、5の倍数・25の倍数・125の倍数…と段階的に5の因数をすべて数え上げることができます。

n = 79 の場合を具体的に見てみましょう。

• 79 ÷ 5 = 15（5の倍数が15個）
• 79 ÷ 25 = 3（25の倍数がさらに3個）
• 79 ÷ 125 = 0（これ以上該当なし）

合計は 15 + 3 = 18 となり、出力結果と一致します。このアルゴリズムの計算量は O(log₅ n) と非常に効率的で、n が大きくなっても高速に動作します。

まとめ

この記事では、Pythonを使って数の階乗に含まれる末尾のゼロの個数をカウントする方法を学びました。階乗の値を実際に計算することなく、5の因数を数えるだけで答えが得られるため、非常に大きな n に対しても実用的なアプローチです。