C言語でストロングナンバー（強数）を判定するプログラムの作り方

ストロングナンバー（強数）とは？

ある数値 n が与えられたとき、その数がストロングナンバー（強数）であるかどうかを判定する方法を解説します。

ストロングナンバーとは、各桁の数字の階乗の総和が元の数値そのものと等しくなる数のことです。階乗とは、その数から1までのすべての正の整数を掛け合わせた値で、「!」（感嘆符）を使って表します。例えば、4! = 4 × 3 × 2 × 1 = 24 となります。

判定の考え方

例として 145 を見てみましょう。まず各桁の数字「1」「4」「5」を取り出し、それぞれの階乗を計算します。

• 1! = 1
• 4! = 24
• 5! = 120

これらを合計すると 1 + 24 + 120 = 145 となり、元の数値と完全に一致します。したがって、145 はストロングナンバーであると言えます。

実行例

入力: n = 124
出力: いいえ、ストロングナンバーではありません
説明: 1! + 2! + 4! = 27 となり、n（= 124）と一致しないため

入力: n = 145
出力: はい、ストロングナンバーです
説明: 1! + 4! + 5! = 145 となり、n と一致するため

解決のためのアプローチ

この問題は、以下の手順に従うことで解くことができます。

• 一の位から順に各桁を取り出し、それぞれの階乗を求める。
• 取り出したすべての桁の階乗を合計する。
• 合計結果を元の数値と比較する。一致すればストロングナンバー、一致しなければストロングナンバーではない。

アルゴリズム

開始
関数 int factorial(int r) 内
    ステップ1 → int型変数 fact を宣言し、1 で初期化する
    ステップ2 → r > 1 の間、以下を繰り返す
        fact に fact * r を代入する
        r を 1 減らす
    ループ終了
    ステップ3 → fact を返す
関数 factorial 終了

関数 int check(int n) 内
    ステップ1 → int型変数 temp、rem、result を宣言し、result を 0 で初期化する
    ステップ2 → temp に n を代入する
    ステップ3 → temp が 0 以外の間、以下を繰り返す
        rem に temp % 10 を代入する
        result に result + factorial(rem) を代入する
        temp に temp / 10 を代入する
    ループ終了
    ステップ4 → result == n であれば
        1 を返す
    ステップ5 → そうでなければ
        0 を返す
関数 check 終了

main(int argc, char const *argv[]) 内
    ステップ1 → 変数 n を宣言し、145 で初期化する
    ステップ2 → check(n) が真であれば
        「Yes it is a strong number」と表示する
    ステップ3 → そうでなければ
        「no it is not a strong number」と表示する
終了

C言語による実装例

#include <stdio.h>
int factorial(int r) {
    int fact = 1;
    while(r>1) {
        fact = fact * r;
        r--;
    }
    return fact;
}
int check(int n) {
    int temp, rem, result = 0;
    temp = n;
    while(temp) {
        rem = temp % 10;
        result = result + factorial(rem);
        temp = temp/10;
    }
    if (result == n)
        return 1;
    else
        return 0;
}
int main(int argc, char const *argv[]) {
    int n = 145;
    if (check(n))
        printf("Yes it is a strong number\n");
    else
        printf("no it is not a strong number\n");
    return 0;
}

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

Yes it is a strong number

補足：既知のストロングナンバー

ストロングナンバーは非常に稀な数として知られており、代表的なものは 1、2、145、40585 の4つだけです。例えば 40585 では、4! + 0! + 5! + 8! + 5! = 24 + 1 + 120 + 40320 + 120 = 40585 となり、条件を満たしていることが確認できます。

本プログラムの計算量は、桁数に比例した O(log₁₀ n) 回のループのみで、各階乗の計算も最大 9! までと小さいため、非常に効率的に動作します。