C#でプロジェクトオイラーを解く（問題２１「友愛数」）

Tweet

Pocket

どーも、みつおです。

友愛数って授業で習いましたっけ？プロジェクトオイラーをやってて初めて聞いた。

問題

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

出典：Problem21

解答

using System;
using System.Collections.Generic;
using System.Linq;

namespace Problem21
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(Solve());
            Console.ReadLine();
        }

        private static int Solve()
        {
            int ret = 0;

            List<int> yuai = new List<int>();

            int b = 0;
            for (int a = 1; a < 10000; a++)
            {
                //aの約数の和
                b = Yakusu(a).Sum();

                //aとbが友愛数であるか判定
                if (a == Yakusu(b).Sum() && a != b)
                {
                    yuai.Add(a);
                }
            }

            //10000未満の友愛数の和
            ret = yuai.Sum();

            return ret;
        }

        private static List<int> Yakusu(int num)
        {
            List<int> ret = new List<int>();

            for(int i = 1;i <= num/2; ++i)
            {
                //割り切れたら、約数のリストに追加
                if (num % i == 0) ret.Add(i);
            }

            return ret;
        }
    }
}

出力

31626