プロジェクトオイラー21

Problem 21 「友愛数」 †

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未満の友愛数の和を求めよ.

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2021




解法
メモ化計算するだけ
Ｃ++

#include<stdio.h>
const int LIMIT=10000;

int main(){
       int yakusu_sum[LIMIT]={0};
       for(int i=1;i<LIMIT;i++){
              for(int j=i*i;j<LIMIT;j+=i){
                     yakusu_sum[j]+=i+(j/i)*(i>1&&i*i!=j);
              }
       }
       int ans=0;
       for(int i=2;i<LIMIT;i++){
              if(yakusu_sum[i]>=LIMIT)continue;
              if(yakusu_sum[i]!=i&&i==yakusu_sum[yakusu_sum[i]])ans+=i;
       }
       printf("%d\n",ans);
}