C++で階乗の桁数を数える方法をわかりやすく解説

本記事では、整数値が与えられたときに、まずその数の階乗を計算し、次にその結果に含まれる桁の総数を求める方法について解説します。

階乗とは何か

階乗とは、ある数から1ずつ減らしながらすべての値を掛け合わせて計算される数です。記号は「!」で表され、0!、1!、2!、3!、5!などのように書きます。なお、0!と1!は常に1となります。

例：2の階乗 = 2 × (2−1) = 2 × 1 = 2
　　3の階乗 = 3 × (3−1) × (2−1) = 3 × 2 × 1 = 6

具体例

入力 − factorial(6)
出力 − factorial(6)の桁数：3

解説 − 6の階乗は720であり、3桁の数字で構成されているため、結果は3になります。

入力 − factorial(12)
出力 − factorial(12)の桁数：9

解説 − 12の階乗は479001600であり、9桁の数字で構成されているため、結果は9になります。

プログラムで使用するアプローチ

• 階乗を計算したい数値を入力として受け取ります。

• 数値が0未満の場合は0を返します。負の数には階乗が存在しないためです。

• 数値が1以下の場合は1を返します。1!は1であり、桁数も1だからです。

• 数値が2以上の場合は、2から始めて入力値以下である間繰り返すループを作成します。

• ループの外側で一時変数（ここではdとします）を0で初期化し、ループ内では各反復ごとにlog10(i)の値を加算していきます。

• 最後に、floor(d)+1 の値（小数点以下を切り捨てて1を足した値）を返します。

• 結果を出力します。

サンプルコード

#include <iostream>
#include <cmath>
using namespace std;
// num! に含まれる桁数を返す関数
int count_digits(int num){
    // 階乗はnum >= 0のときのみ存在する
    if (num < 0){
       return 0;
    }
    // 基本ケース
    if (num <= 1){
       return 1;
    }
    // それ以外はnumまで反復して値を計算する
    double d = 0;
    for (int i=2; i<=num; i++){
       d += log10(i);
    }
    return floor(d) + 1;
}
int main(){
    cout<<"number of digits in factorial(1) is: "<<count_digits(1)<< endl;
    cout<<"number of digits in factorial(6) is: "<<count_digits(6) << endl;
    cout<<"number of digits in factorial(106) is: "<<count_digits(106) << endl;
    return 0;
}

実行結果

上記のコードを実行すると、次のような出力が生成されます。

number of digits in factorial(1) is: 1
number of digits in factorial(6) is: 3
number of digits in factorial(106) is: 171

まとめ

階乗の値は非常に大きくなるため、実際に掛け算を行って桁数を数えるのは非効率です。対数の性質「log(a×b) = log(a) + log(b)」を利用すれば、大きな数を直接計算することなく桁数を求められます。このテクニックは競技プログラミングなどでも役立つので、ぜひ覚えておきましょう。