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

Problem21 10000未満の友愛数の合計

問題

d(n)をnの真の約数の和と定義する。(真の約数とはn以外の約数のことである。)
もし、d(a) = b かつ d(b) = a (a ≠ b)を満たすとき、aとbは友愛数(親和数)であるという。

例えば、220の約数は1,2,4,5,10,11,20,22,44,55,110なのでd(220) = 284である。
また、284の約数は1,2,4,71,142なのでd(284) = 220である。

それでは10000未満の友愛数の合計を求めよ。


ソース

#include <stdio.h>

int GetD(int hiki);

void main()
{
    int SumVal = 0;
    for (int I = 1; I < 10000; I++) {
        int SavedGetD = GetD(I);
        if(I== GetD(SavedGetD) && I<SavedGetD){
            printf("%dと%dは友愛数\n",I,SavedGetD);
            SumVal += I + SavedGetD;
        }
    }
    printf("友愛数の合計=%d\n",SumVal);
}

int GetD(int hiki)
{
    int WillReturn=0;
    for(int I=1;I*2<=hiki;I++){
        if(hiki%I==0 && hiki!=I){
            WillReturn+=I;
        }
    }
    return WillReturn;
}


実行結果

220と284は友愛数
1184と1210は友愛数
2620と2924は友愛数
5020と5564は友愛数
6232と6368は友愛数
友愛数の合計=31626


解説

int SavedGetD = GetD(I);
で計算結果をキャッシュしてます。