トップページに戻る    次のC++のサンプルへ    前のC++のサンプルへ

Problem34 各桁の数の階乗の和が自分自身と一致する数

問題

145は面白い数である。
1! + 4! + 5! = 1 + 24 + 120 = 145となる。
各桁の数の階乗の和が自分自身と一致する数の総和を求めよ。

注: 1! = 1 と 2! = 2 は総和に含めてはならない。


ソース

#include <stdio.h>

int CalcKaijyo(int n);

void main()
{
    int Answer = 0;
    for (int I = 3; I <= 2540160; I++) {
        int KaijyoSum = 0;
        int CopiedVal = I;
        do{
            KaijyoSum += CalcKaijyo(CopiedVal%10);
            if (I < KaijyoSum) break;
            CopiedVal /=10;
        } while (CopiedVal > 0);
        if (I == KaijyoSum) {
            printf("%dの各桁の数の階乗の和が、自分自身と一致\n",I);
            Answer += I;
        }
    }
    printf("答えは%d\n",Answer);
}

int CalcKaijyo(int n)
{
    if (n == 0) return 1;
    if (n == 1) return 1;
    int WillReturn = 1;
    for (int I = 2; I <= n; I++) WillReturn *= I;
    return WillReturn;
}


実行結果

145の各桁の数の階乗の和が、自分自身と一致
40585の各桁の数の階乗の和が、自分自身と一致
答えは40730


解説

9の階乗 = 362880
よって、
1桁の最大値 362880*1= 362880
2桁の最大値 362880*2= 725760
3桁の最大値 362880*3=1088640
4桁の最大値 362880*4=1451520
5桁の最大値 362880*5=1814400
6桁の最大値 362880*6=2177280
7桁の最大値 362880*7=2540160
8桁の最大値 362880*8=2903040
9桁の最大値 362880*9=3265920

よって、調べる数の上限を7桁の最大値である2540160としてます。

8桁は、調べても無駄であり、
7桁も2540160より大きい数は調べても無駄であるからです。