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個以上の約数をもつ最初の三角数はいくらか。

ソース

#include <stdio.h>
#include <limits.h>

void main()
{
    //const int TargetCount = 6;
    const int TargetCount = 501;

    int wkSankakusuu = 0;
    for (int I = 1; I < INT_MAX; I++) {
        wkSankakusuu += I;

        int YakusuuCnt = 1;
        int copiedSankakusuu = wkSankakusuu;
        for (int J = 2; J <= copiedSankakusuu; J++) {
            if (copiedSankakusuu % J == 0) {
                int WillProdVal = 1;
                while (copiedSankakusuu % J == 0) {
                    copiedSankakusuu /= J;
                    WillProdVal++;
                }
                YakusuuCnt *= WillProdVal;
            }
        }
        printf("%dの約数は%d個\n",wkSankakusuu,YakusuuCnt);
        if (YakusuuCnt >= TargetCount) return;
    }
}

実行結果

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

解説

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