C++で階乗がxで割り切れる最小の自然数を求める方法

問題概要

階乗の値が与えられた整数 x で割り切れる、最初の自然数 N を求めるプログラムを作成します。x の値はユーザーから入力されるものとします。

例えば、x = 16 の場合、答えは 6 になります。これは 6! = 720 であり、720 mod 16 = 0 となるためです。つまり、6! は 16 で割り切れる最小の階乗ということになります。

解法のアプローチ

この問題は、シンプルな反復処理（総当たり）で解くことができます。手順は以下の通りです。

1. 1 から順に階乗を計算していきます（1!, 2!, 3!, …）
2. 各階乗の値を x で割った余り（剰余）を確認します
3. 余りが 0 になった時点で処理を停止し、そのときの数を結果として返します

C++による実装例

#include<iostream>
using namespace std;

int getNumber(int x) {
    int fact = 1;  // 階乗の値を保持する変数
    int i = 0;
    while (fact % x != 0) {  // xで割り切れるまで繰り返す
        i++;
        fact = fact * i;  // 階乗を累積計算
    }
    return i;
}

int main() {
    int x = 16;
    cout << "Minimum value of N is: " << getNumber(x);
}

実行結果

Minimum value of N is: 6

コードの解説

このプログラムの動作を順を追って説明します。

• 変数 fact は階乗の値を累積的に保持します。初期値は 1 です。
• 変数 i は現在の自然数を表し、ループのたびに 1 ずつ増加します。
• while ループでは fact % x != 0、つまり階乗が x で割り切れない間、処理を継続します。
• ループ内で i を増やし、fact に掛け合わせることで 1!, 2!, 3!, … と順番に階乗を計算します。
• 剰余が 0 になった瞬間にループを抜け、そのときの i の値を返します。

注意点と改良のヒント

この実装はシンプルで分かりやすい反面、x の値が大きい場合には注意が必要です。階乗の値は急激に増大するため、int 型ではすぐにオーバーフローしてしまいます。その場合は long long 型を使用するか、x を素因数分解し、各素因数のべき乗が階乗に含まれる最小の n を求める方法が有効です。素因数分解を利用すれば、大きな x に対しても高速に答えを求められます。