Problem49 素数の等差数列

問題

項差3330の等差数列1487, 4817, 8147は次の2つの変わった性質を持つ.

・3つの項はそれぞれ素数である.
・各項は他の項の置換で表される.

1,2,3桁の素数にはこのような性質を持った数列は存在しないが,
4桁の増加列には、もう1つ存在する.
それではこの数列の3つの項を連結した12桁の数を求めよ.

ソース

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

class Program
{
    const int Jyougen = 9999;

    static int[] mSosuuArr = new int[Jyougen + 1];

    //エラトステネスの篩
    static void Eratosthenes()
    {
        for (int I = 2; I <= mSosuuArr.GetUpperBound(0); I++) {
            mSosuuArr[I] = I;
        }
        for (int I = 2; I * I <= mSosuuArr.GetUpperBound(0); I++) {
            if (I != 2 && I % 2 == 0) continue;

            if (mSosuuArr[I] != 0) {
                for (int J = I * 2; J <= mSosuuArr.GetUpperBound(0); J += I) {
                    mSosuuArr[J] = 0;
                }
            }
        }
        mSosuuArr = mSosuuArr.Where(X => X != 0).Where(X => 1000 <= X).ToArray();
    }

    static void Main()
    {
        Eratosthenes();

        var Stk = new Stack<List<int>>();
        for (int I = 0; I <= mSosuuArr.GetUpperBound(0); I++) {
            if (mSosuuArr[I] == 1487) continue;
            Stk.Push(new List<int>() { mSosuuArr[I] });
        }

        while (Stk.Count > 0) {
            List<int> PoppedList = Stk.Pop();

            if (PoppedList.Count == 3) {
                Console.Write("Answer=");
                PoppedList.ForEach(A => Console.Write(A));
                Console.WriteLine();
                continue;
            }

            int LastVal = PoppedList[PoppedList.Count - 1];
            foreach (int EachSosuu in mSosuuArr.Where(X => LastVal < X)) {
                //条件1 3項目が9999を超えないこと
                if (PoppedList.Count == 1) {
                    int Kousa1 = EachSosuu - LastVal;
                    if (EachSosuu + Kousa1 > Jyougen) break;
                }

                //条件2 等差数列であること
                if (PoppedList.Count == 2) {
                    int Kousa2 = PoppedList[1] - PoppedList[0];
                    if (PoppedList[1] + Kousa2 < EachSosuu) break;
                    if (PoppedList[1] + Kousa2 > EachSosuu) continue;
                }

                //条件3 数字が一致すること
                var HashSet1 = new HashSet<char>(LastVal.ToString());
                var HashSet2 = new HashSet<char>(EachSosuu.ToString());
                if (HashSet1.SetEquals(HashSet2) == false) continue;

                var WillPushList = new List<int>(PoppedList);
                WillPushList.Add(EachSosuu);
                Stk.Push(WillPushList);
            }
        }
    }
}

実行結果

Answer=296962999629

解説

エラトステネスの篩で4桁の素数を列挙してから、
昇順で深さ優先探索してます。