JavaScriptで階乗の末尾にあるゼロの個数を求める方法

整数 n が与えられたとき、n!(階乗)の末尾に連続して現れるゼロの個数を返す関数を作成します。

例えば、以下のようになります。

trailingZeroes(4) = 0
trailingZeroes(5) = 1  // 5! = 120 のため
trailingZeroes(6) = 1

考え方

階乗の末尾のゼロは、「2 × 5 = 10」というペアがいくつ作られるかによって決まります。階乗の中では2の個数が5の個数より常に多いため、約数として含まれる5の個数を数えれば、末尾のゼロの個数と一致します。

具体的には、n / 5 で5の倍数の個数を、n / 25 で25(= 5²)の倍数の個数を、というように5の冪乗ごとに加算していきます。

サンプルコード

const num = 17;

const findTrailingZeroes = num => {
    let cur = 5, total = 0;
    while (cur <= num) {
        total += Math.floor(num / cur);
        cur *= 5;
    };
    return total;
};

console.log(findTrailingZeroes(num)); // 17!
console.log(findTrailingZeroes(5));   // 5!
console.log(findTrailingZeroes(1));   // 1!

実行結果

コンソールには以下のように出力されます。

3
1
0

解説

• findTrailingZeroes(17) → 3:17 ÷ 5 = 3(余り切り捨て)、17 ÷ 25 = 0 なので合計は 3 です。実際、17! = 355687428096000 となり、末尾にゼロが3つ並びます。
• findTrailingZeroes(5) → 1:5! = 120 のため、末尾のゼロは1個です。
• findTrailingZeroes(1) → 0:1! = 1 なので、末尾のゼロは存在しません。

このアルゴリズムはループ回数が log₅(n) 程度しかないため、非常に大きな n に対しても高速に動作します。