Problem179 連続する正の約数

問題

n と n + 1 の正の約数の数が同じになる 1 < n < 10の7乗 の整数は幾つあるか.

例として,
14 の正の約数は 1, 2, 7, 14 であり,
15 の正の約数は 1, 3, 5, 15 である.

ソース

using System;
using System.Collections.Generic;

class Program
{
    const int Jyougen = 10000000;

    static int[] SosuuArr;

    //エラトステネスの篩
    static void Eratosthenes()
    {
        var IsSouuArr = new System.Collections.BitArray(Jyougen + 1);

        for (int I = 2; I <= IsSouuArr.Count - 1; I++) {
            IsSouuArr[I] = true;
        }
        for (int I = 2; I * I <= IsSouuArr.Count - 1; I++) {
            if (I != 2 && I % 2 == 0) continue;

            if (IsSouuArr[I]) {
                for (int J = I * 2; J <= IsSouuArr.Count - 1; J += I) {
                    IsSouuArr[J] = false;
                }
            }
        }
        var SosuuList = new List<int>();
        for (int I = 2; I <= IsSouuArr.Count - 1; I++)
            if (IsSouuArr[I]) SosuuList.Add(I);

        SosuuArr = SosuuList.ToArray();
    }

    static int DeriveYakusuuCnt(int pVal)
    {
        if (Array.BinarySearch<int>(SosuuArr, pVal) >= 0) return 2;

        int CopiedVal = pVal;
        int YakusuuCnt = 1;

        int I = 0;
        while (true) {
            if (CopiedVal % SosuuArr[I] == 0) {
                int WillProd = 0;
                do {
                    WillProd++;
                    CopiedVal /= SosuuArr[I];
                } while (CopiedVal % SosuuArr[I] == 0);
                YakusuuCnt *= (WillProd + 1); //積の法則

                if (CopiedVal == 1) return YakusuuCnt;

                if (Array.BinarySearch<int>(SosuuArr, I, SosuuArr.Length - I, CopiedVal) >= 0)
                    return YakusuuCnt * 2;
            }
            I++;
        }
    }

    static void Main()
    {
        var sw = System.Diagnostics.Stopwatch.StartNew();

        Eratosthenes();

        int AnswerCnt = 0;
        int YakusuuCntCurr = 2;
        int YakusuuCntNext;
        for (int I = 2; I <= 10000000 - 1; I++) {
            YakusuuCntNext = DeriveYakusuuCnt(I + 1);
            //Console.WriteLine("{0}の約数は{1}個", I, YakusuuCntCurr);

            if (YakusuuCntCurr == YakusuuCntNext) {
                AnswerCnt++;
            }
            YakusuuCntCurr = YakusuuCntNext;
        }
        Console.WriteLine("解は{0}。経過時間={1}", AnswerCnt, sw.Elapsed);
    }
}

実行結果

解は986262。経過時間=00:00:07.1859711

解説

素因数分解と積の法則で、約数の数を求めてます。