C#でプロジェクトオイラーを解く（問題１２「高度整除三角数」）

Tweet

Pocket

どーも、みつおです。

素因数分解は「C#で素因数分解」のページを参考させてもらいました。

問題

三角数の数列は自然数の和で表わされ, 7番目の三角数は 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 である. 三角数の最初の10項は:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

となる.

最初の7項について, その約数を列挙すると, 以下のとおり.

 1: 1
 3: 1,3
 6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

これから, 7番目の三角数である28は, 5個より多く約数をもつ最初の三角数であることが分かる.

では, 500個より多く約数をもつ最初の三角数はいくつか.

出典：Problem12

解答

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

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

        private static int Solve()
        {
            int ret = 0;
            int cnt = 0;
            int i = 0;
            List<int> data = new List<int>();

            //500個より多くの約数の個数が見つかるまでループ
            while(cnt < 500)
            {
                i++;
                //自然数のデータを作成
                data.Add(i);
                
                //自然数の和を引数に取り、約数の個数を返す
                cnt = YakusuCount(data.Sum());
            }

            //三角数を計算
            ret = data.Sum();

            return ret;
        }

        private static int YakusuCount(int no)
        {
            List<int> kosu = new List<int>();

            //素因数分解を求める
            var soinsulist = SoinsuBunkai(no);
            if (soinsulist.Count() < 1) return 0;
            
            //素因数分解をグループ化
            var group = soinsulist.GroupBy(a => a);

            foreach (var item in group)
            {
                kosu.Add(item.Count() + 1);
            }

            //約数の個数は素因数分解の個数をかけたもの
            int product = kosu.Aggregate((now, next) => now * next);

            return product;
        }

        public static IEnumerable<int> SoinsuBunkai(int n)
        {
            int i = 2;
            int tmp = n;

            while (i * i <= n)
            {
                if (tmp % i == 0)
                {
                    tmp /= i;
                    yield return i;
                }
                else i++;
            }

            if (tmp != 1) yield return tmp;
        }
    }
}

出力

76576500