C++でクリシュナムルティ数かどうかを判定する方法

クリシュナムルティ数とは

クリシュナムルティ数（Krishnamurty Number）とは、各桁の数字の階乗の合計が元の数そのものと等しくなる特別な数のことです。例えば、145という数値を見てみましょう。1! + 4! + 5! = 1 + 24 + 120 = 145 となり、各桁の階乗の合計が元の数と一致します。したがって、145はクリシュナムルティ数です。

この性質を持つ数は非常に珍しく、代表的な例としては 1、2、145、40585 などが挙げられます。

判定アルゴリズムの考え方

判定ロジックはシンプルで、以下の手順で処理を行います。

1. 対象の数値から一桁ずつ数字を取り出す
2. 取り出した数字それぞれの階乗を計算し、合計に加算していく
3. すべての桁の処理が終わったら、合計が元の数値と一致しているかどうかを確認する

それでは、実際のコードを見ながら理解を深めましょう。

C++での実装例

#include <iostream>
#include <cmath>
using namespace std;

// 階乗を再帰的に計算する関数
long factorial(int n) {
    if(n <= 1){
        return 1;
    }
    return n * factorial(n - 1);
}

// クリシュナムルティ数かどうかを判定する関数
bool isKrishnamurty(int number) {
    int temp = number;
    int sum = 0;
    while(number > 0){
        sum += factorial(number % 10); // 各桁の階乗を加算
        number /= 10;                  // 次の桁へ移動
    }
    if(sum == temp){
        return true;
    }
    return false;
}

int main() {
    int n = 145;
    if(isKrishnamurty(n)){
        cout << n << " is Krishnamurty Number";
    } else {
        cout << n << " is not Krishnamurty Number";
    }
}

コードの解説

• factorial関数： 再帰呼び出しを利用して引数 n の階乗を計算します。n が 1 以下になった時点で 1 を返すことで再帰を終了します。
• isKrishnamurty関数： number % 10 で最下位の桁を取り出し、その階乗を合計に加算します。その後 number /= 10 で桁を一つずらし、全桁を処理するまで繰り返します。
• 判定部分： 計算した合計 sum が元の数値 temp と一致すれば true を返し、クリシュナムルティ数であると判定します。

実行結果

145 is Krishnamurty Number

このように、各桁の階乗の合計を求めて元の数と比較するだけで、簡単にクリシュナムルティ数を判定できます。計算量は桁数に依存するため、大きな数でも高速に処理できるのが特徴です。