Problem47 連続する4つの数がそれぞれ4つの異なる素因数

問題

連続する2つの数がそれぞれ2つの異なる素因数を持つのは
    14 = 2*7
    15 = 3*5 の場合である

同様に連続する3つの数がそれぞれ3つの異なる素因数を持つのは
    644 = 2の2乗*7*23
    645 = 3*5*43
    646 = 2*17*19 の場合である

連続する4つの数がそれぞれ4つの異なる素因数を持つ場合を考え、連続する数の中で最小のものを答えよ

ソース

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

class Program
{
    //const int NeedPair = 2;
    //const int NeedPair = 3;
    const int NeedPair = 4;

    const int Jyougen = 135000;

    static int[] mSosuuArr;

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

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

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

        mSosuuArr = SosuuList.ToArray();
    }

    static void Main()
    {
        Eratosthenes();

        var SoinsuuBunkaiDict = new Dictionary<int, int[]>();

        for (int I = 2; I <= Jyougen; I++) {
            int[] SoinsuuArr = DeriveSoinsuuArr(I);
            string WillOut = string.Format("{0}の素因数は", I);
            Array.ForEach(SoinsuuArr, A => WillOut += string.Format("{0},", A));
            Console.WriteLine(WillOut);

            SoinsuuBunkaiDict.Add(I, SoinsuuArr);
            if (SoinsuuBunkaiDict[I].Length == NeedPair
             && SoinsuuBunkaiDict.Count >= NeedPair) {
                bool IsOK = true;
                for (int J = I - NeedPair + 1; J <= I - 1; J++) {
                    if (SoinsuuBunkaiDict[J].Length != NeedPair) {
                        IsOK = false;
                        break;
                    }
                }
                if (IsOK) {
                    Console.WriteLine("Answer={0}", I - NeedPair + 1);
                    return;
                }
            }
            if (I % 10000 == 0) { //Dictionaryから不要になったキーをRemove
                foreach (int AnyInt in SoinsuuBunkaiDict.Keys.Where(X => X < I - NeedPair).ToArray()) {
                    SoinsuuBunkaiDict.Remove(AnyInt);
                }
            }
        }
    }

    static int[] DeriveSoinsuuArr(int pTarget)
    {
        if (Array.BinarySearch<int>(mSosuuArr, pTarget) >= 0)
            return new int[] { pTarget };

        var SoinsuuList = new List<int>();
        for (int I = 0; I <= mSosuuArr.GetUpperBound(0); I++) {
            bool FirstFlag = true;
            while (pTarget % mSosuuArr[I] == 0) {
                if (FirstFlag) {
                    FirstFlag = false;
                    SoinsuuList.Add(mSosuuArr[I]);
                }
                pTarget /= mSosuuArr[I];
            }
            if (pTarget == 1) break;
        }
        return SoinsuuList.ToArray();
    }
}

実行結果

省略
00:00:21.9581494。134041の素因数は311,431,
00:00:21.9586355。134042の素因数は2,67021,
00:00:21.9587020。134043の素因数は3,7,13,491,
00:00:21.9587634。134044の素因数は2,23,31,47,
00:00:21.9588252。134045の素因数は5,17,19,83,
00:00:21.9588933。134046の素因数は2,3,11,677,
Answer=134043

解説

Dictionaryジェネリックで素因数分解の結果をキャッシュしつつ、
Removeメソッドで不要になったキーをRemoveしてます。
MSDN --- Dictionary<TKey, TValue>.Remove メソッド