C#でプロジェクトオイラーを解く（問題２３「非過剰数和」）

Tweet

Pocket

どーも、みつおです。

最初、この問題の意味が不明だったから、かなり解答に時間がかかった。。。

問題

完全数とは, その数の真の約数の和がそれ自身と一致する数のことである. たとえば, 28の真の約数の和は, 1 + 2 + 4 + 7 + 14 = 28 であるので, 28は完全数である.

真の約数の和がその数よりも少ないものを不足数といい, 真の約数の和がその数よりも大きいものを過剰数と呼ぶ.

12は, 1 + 2 + 3 + 4 + 6 = 16 となるので, 最小の過剰数である. よって2つの過剰数の和で書ける最少の数は24である. 数学的な解析により, 28123より大きい任意の整数は2つの過剰数の和で書けることが知られている. 2つの過剰数の和で表せない最大の数がこの上限よりも小さいことは分かっているのだが, この上限を減らすことが出来ていない.

2つの過剰数の和で書き表せない正の整数の総和を求めよ.

出典：Problem23

解答

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

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

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

            //過剰数のリストを作成
            var list = Enumerable.Range(1, limit)
                       .Where(tmp => IsKazyosu(tmp))
                       .ToList();

            //過剰数の和のリストを作成
            var kazyo = KazyosuNoWa(list).ToList();
            var find = kazyo.FindAll(tmp => tmp < limit);

            //28123までループ
            for (int i = 0;i <= limit; i++)
            {
                //過剰数の和であるか判定
                int tst = kazyo.Find(t => t == i);

                //過剰数でないなら足していく
                if (tst < 1) ret += i;
            }

            return ret;
        }

        private static bool IsKazyosu(int n)
        {
            long ret = 0;

            //約数の和を求める
            for (int i = 1; i <= n / 2; i++)
            {
                if (n % i == 0) ret += i;
            }

            //約数の和がその数よりも大きい（過剰数）か判定
            return ret > n;
        }

        private static IEnumerable<int> KazyosuNoWa(List<int> list)
        {
            List<int> tmp = new List<int>();
            int sum = 0;

            foreach(var a in list)
            {
                foreach(var b in list)
                {
                    //過剰数の和をリストに追加
                    sum = a + b;
                    tmp.Add(sum);
                }
            }

            //重複削除
            IEnumerable<int> ret = tmp.Distinct().OrderBy(a => a);
            
            return ret;
        }
    }
}

出力

4179871