【C言語】階乗の末尾に連続するゼロ(後続ゼロ)の個数を求めるプログラム

階乗の後続ゼロとは

与えられた階乗(n!)の計算結果において、末尾に連続して並ぶ0(後続ゼロ・トレーリングゼロ)の個数を求める方法を、具体的な例を挙げながら解説します。

例1

入力:4

出力:0

解説:4! = 24 となり、末尾にゼロは存在しません。4! = 4 × 3 × 2 × 1 = 24 であり、一の位には「4」が来るため、後続ゼロは0個です。

例2

入力:6

出力:1

解説:6! = 720 となり、末尾のゼロは1個です。6! = 6 × 5 × 4 × 3 × 2 × 1 = 720 であり、一の位が「0」になるため、後続ゼロは1個となります。

例3

入力は以下の通りです。

n = 4
n = 5

出力は以下の通りです。

4! の後続ゼロの個数:0

5! の後続ゼロの個数:1

後続ゼロを求める考え方

階乗の末尾に0が現れるのは、その数が10(= 2 × 5)を約数として持つ場合です。階乗の素因数分解では、2の個数よりも5の個数の方が必ず少なくなるため、「因数5がいくつ含まれるか」を数えれば後続ゼロの個数が求まります。

具体的には、n を5で割った商を順に加算していきます。25 = 5 × 5 のように5が複数回現れる数も存在するため、商が0になるまで繰り返し5で割り続けるのがポイントです。

Cプログラム例

以下は、与えられた階乗の後続ゼロを求めるCプログラムです。

#include <stdio.h>
static int trailing_Zeroes(int n){
    int number = 0;
    while (n > 0) {
        number += n / 5;
        n /= 5;
    }
    return number;
}
int main(void){
    int n;
    printf("enter integer1:");
    scanf("%d",&n);
    printf("
 no: of trailing zeroe's of factorial %d is %d

 ", n, trailing_Zeroes(n));
    printf("enter integer2:");
    scanf("%d",&n);
    printf("
 no: of trailing zeroe's of factorial %d is %d ", n, trailing_Zeroes(n));
    return 0;
}

プログラムの仕組み

trailing_Zeroes 関数では、引数 n が0より大きい間、n / 5 の商を変数 number に加算し、n 自身も5で割って更新します。この処理により、5の倍数・25の倍数・125の倍数といった具合に段階的にカウントされ、正確な後続ゼロの個数が得られます。

実行結果

上記のプログラムを実行すると、次のような結果が出力されます。

enter integer1:5
no: of trailing zeroe's of factorial 5 is 1
enter integer2:6
no: of trailing zeroe's of factorial 6 is 1