C++で階乗が計算できる整数の最大値を見つける方法

この記事では、C++の環境で階乗（factorial）の計算が可能な整数の最大値を求めるプログラムの作成方法について解説します。

ある数の階乗とは、その数までのすべての整数を掛け合わせた値であり、非常に大きな数になります。C++の組み込みデータ型では、扱える数値の大きさに上限があるため、どこまでの階乗が計算できるのか、その限界を調べる必要があります。

解決のアプローチ

ここで利用するのは、データ型のオーバーフローの性質です。符号付き整数型では、格納できる最大値を超えると、値が負の数として返される（オーバーフローする）という特性があります。この挙動を検出することで、階乗の計算限界を特定できます。

使用するデータ型は long long int です。これはC++の基本的な整数型の中で最も大きい範囲を持つ型であり、通常は64ビットで表現されます。

アルゴリズムの流れ

1. 変数 maxVal を1に初期化し、long long int 型の maxFactorial も1に初期化します。
2. 無限ループの中で、maxFactorial が負になったかどうかを判定します。
3. 負になった場合、直前の値（maxVal - 1）が階乗計算可能な最大値となるため、それを返します。
4. そうでなければ maxVal をインクリメントし、maxFactorial に掛け合わせて処理を続行します。

サンプルコード

#include <iostream>
using namespace std;
int calcMaxFactVal(){
    int maxVal = 1;
    long long int maxFactorial = 1;
    while (true){
        if (maxFactorial < 0)
            return (maxVal - 1);
        maxVal++;
        maxFactorial *= maxVal;
    }
    return -1;
}
int main(){
    cout<<"The maximum value of an integer for which factorial can be calculated on machine is "<<calcMaxFactVal();
    return 0;
}

実行結果

The maximum value of an integer for which factorial can be calculated on machine is 20

結果の考察

実行結果から、long long int 型を使用した場合、20の階乗（20! = 2,432,902,008,176,640,000）までは正しく計算できることがわかります。21! は long long int の最大値（約9.22×10^18）を超えるため、オーバーフローして負の値になってしまいます。

なお、より大きな階乗を扱いたい場合は、多倍長整数ライブラリや文字列による演算の実装など、別の手法を検討する必要があります。