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未満の友愛数の合計を求めよ。

ソース

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        int SumVal = 0;
        for (int I = 1; I < 10000; I++) {
            int wkD = DeriveD(I);
            if (DeriveD(wkD) == I && I < wkD) {
                Console.WriteLine("{0}と{1}は友愛数", I, wkD);
                SumVal += I + wkD;
            }
        }
        Console.WriteLine("友愛数の合計={0}", SumVal);
    }

    //真の約数の和を求める
    static int DeriveD(int pTarget)
    {
        var YakusuuSet = new HashSet<int>();

        for (int I = 1; I * I <= pTarget; I++) {
            if (pTarget % I == 0) {
                YakusuuSet.Add(I);
                YakusuuSet.Add(pTarget / I);
            }
        }

        int WillReturn = 0;
        foreach (int EachInt in YakusuuSet) {
            if (EachInt != pTarget)
                WillReturn += EachInt;
        }
        return WillReturn;
    }
}

実行結果

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

解説

HashSetで真の約数を管理してます。