C++で指定された範囲内の階乗数の個数を数える方法

整数値が格納された変数startから変数endまでの範囲が与えられ、その範囲内に存在する階乗数の総数を求めるのがこの課題です。

階乗数とは

ある数の階乗とは、その数から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

具体例

入力 − start = 5, end = 600
出力 − 階乗数の個数は 3

説明 − 5〜600の範囲内に存在する階乗数は、6（3!）、24（4!）、120（5!）の3つです。

入力 − start = 1, end = 100
出力 − 階乗数の個数は 5

説明 − 1〜100の範囲内には、1（0!・1!）、2（2!）、6（3!）、24（4!）という階乗数が存在します。0!と1!が同じ値1になるため、プログラム上では1が2回カウントされ、合計5が返されます。

プログラムで使うアプローチ

• 範囲を入力として受け取り、変数startとendに格納します。

• 階乗値を保存するための変数factを1で初期化し、数を増やしていくための一時変数iも用意します。

• factがstart未満である間ループを回し、factにiを掛けて階乗を計算しながら、iの値も増やしていきます。

• 続いて、factがend以下である間もう一つのループを回し、カウント用変数rを増加させながらfactにiを掛け、iも増やしていきます。

• 最後に、階乗数の総数を保持している変数rの値を返します。

• 結果を出力します。

コード例

#include <iostream>
using namespace std;
// 階乗の個数を数える関数
int factorials(int start, int end){
    // 1から始めて、start以上になる最初の階乗数factを探す
    int fact = 1, i = 1;
    while (fact < start){
        fact = fact * i;
        i++;
    }
    // start〜endの範囲内の階乗数を数えるカウンタr
    int r = 0;
    while (fact <= end){
        r++;
        fact = fact * i;
        i++;
    }
    // 範囲内の階乗の個数を返す
    return r;
}
int main(){
    int start = 5, end = 600;
    cout << "Count of factorial numbers are " << factorials(start, end);
    return 0;
}

出力

上記のコードを実行すると、次の出力が得られます。

Count of factorial numbers are 3

補足：計算量と注意点

このアルゴリズムは階乗を順番に生成しながら比較していくだけなので非常に効率的で、階乗は爆発的に増加するためループの反復回数はごくわずかで済みます。ただし、12!（4,790,016,000）は32ビットint型の最大値（約21.4億）を超えるため、より大きな範囲を扱う場合はlong long型などの使用を検討してください。