トップページに戻る
次の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);
で計算結果をキャッシュしてます。