Javaで階乗の末尾ゼロの個数を効率的に求めるプログラム

ある数の階乗(n!)を計算したとき、その結果の末尾に連続して並ぶゼロ(後続ゼロ・トレーリングゼロ)の個数を求めるのは、Javaプログラミングで頻出する定番のアルゴリズム問題です。以下にJavaでの実装例を示します。

考え方

階乗の末尾にゼロが現れるのは、10 = 2 × 5 という因数同士が掛け合わさったときです。階乗の中では2の因数の数が5の因数の数よりも必ず多くなるため、末尾ゼロの個数は「1からnまでの各整数に含まれる5の因数の総数」と一致します。この性質を利用すれば、巨大な階乗を実際に計算することなく、効率的に答えを求めることができます。

サンプルコード

import java.io.*;
public class Demo{
    static int trailing_zero(int num){
        int count = 0;
        for (int i = 5; num / i >= 1; i *= 5){
            count += num / i;
        }
        return count;
    }
    public static void main (String[] args){
        int num = 1000000;
        System.out.println("The number of trailing zeroes in " + num +" factorial is " +
        trailing_zero(num));
    }
}

実行結果

The number of trailing zeroes in 1000000 factorial is 249998

コードの解説

Demoクラスには、trailing_zeroというメソッドが定義されています。まずカウント用の変数countを0で初期化し、ループ変数iを5から始めて、num / i >= 1が成り立つ間、iを5倍ずつ増やしながら処理を繰り返します。

各ループで num / i の値を加算していくことで、「5の倍数の個数」「25の倍数の個数」「125の倍数の個数」…といったように、5のべき乗ごとの寄与分を累積していきます。これは数学で知られるルジャンドルの公式に基づく手法です。最終的なcountの値が末尾ゼロの個数となり、メソッドの戻り値として返されます。

mainメソッドでは、変数numに1000000を設定し、その値を引数としてtrailing_zeroメソッドを呼び出します。得られた結果は、説明メッセージとともにコンソールへ出力されます。

計算量とメリット

このアルゴリズムの時間計算量は O(log₅ n) と非常に効率的で、nが大きくなっても高速に動作します。また、階乗そのものを計算しないため、int型やlong型のオーバーフローを気にする必要がない点も大きな利点です。