Problem12 501個以上の約数をもつ最初の三角数

問題

三角数の数列は自然数の和で表わされ、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は、6個以上の約数をもつ最初の三角数であることが分る。
では、501個以上の約数をもつ最初の三角数はいくらか。

ソース

using System;

class Program
{
    //const int TargetCount = 6;
    const int TargetCount = 501;

    static void Main()
    {
        int CurrSankakusuu = 0;
        for (int I = 1; I < int.MaxValue; I++) {
            CurrSankakusuu += I;

            int YakusuuCnt = 1;
            int CopiedSankakusuu = CurrSankakusuu;
            for (int J = 2; J <= CopiedSankakusuu; J++) {
                if (CopiedSankakusuu % J == 0) {
                    int WillProd = 1;
                    while (CopiedSankakusuu % J == 0) {
                        CopiedSankakusuu /= J;
                        WillProd++;
                    }
                    YakusuuCnt *= WillProd;
                }
            }
            Console.WriteLine("{0}の約数は{1}個", CurrSankakusuu, YakusuuCnt);
            if (YakusuuCnt >= TargetCount)
                return;
        }
    }
}

実行結果

省略
76502265の約数は64個
76514635の約数は16個
76527006の約数は32個
76539378の約数は16個
76551751の約数は8個
76564125の約数は96個
76576500の約数は576個

解説

三角数を素因数分解して、積の法則を適用して、約数の数を求めてます。