C++でn以下のすべての階乗数を効率的に求める方法

本記事では、C++を使ってn以下のすべての階乗数を出力する方法を解説します。

階乗数とは

階乗数（factorial number）とは、ある正の整数の階乗として表せる数のことです。たとえば、1! = 1、2! = 2、3! = 6、4! = 24、5! = 120 となるため、1、2、6、24、120 はいずれも階乗数に該当します。

アルゴリズムの考え方

n以下の階乗数を求める際、毎回ゼロから階乗を計算し直す必要はありません。初期値として fact = 1 を用意し、変数 i を 2 から順に増やしながら fact に i を掛けていくだけで、1!、2!、3!、… と次々に求められます。fact が n を超えた時点でループを終了すればよいため、非常にシンプルかつ効率的な手法です。

処理の手順

1. fact = 1、i = 2 で初期化する
2. fact が n 以下である限り、fact を出力する
3. fact に i を掛け、その後 i をインクリメントする
4. fact が n を超えたら処理を終了する

C++での実装例

#include <iostream>
using namespace std;

void getFactorialNumbers(int n) {
    int fact = 1;
    int i = 2;
    while (fact <= n) {
        cout << fact << " ";
        fact = fact * i;
        i++;
    }
}

int main() {
    int n = 150;
    getFactorialNumbers(n);
}

実行結果

1 2 6 24 120

まとめ

この方法では、各階乗を直前の階乗に対して1回の掛け算を行うだけで求められるため、無駄な再計算が発生しません。階乗は極めて速く増加するため、nが大きくなってもループの反復回数はごくわずかで済みます。n以下の階乗数を列挙したい場合に、ぜひ活用してみてください。