Problem51 素数の桁置換

問題

*3の第1桁を置き換えることで, 13, 23, 43, 53, 73, 83という6つの素数が得られる.

56**3の第3桁と第4桁を同じ数で置き換えることを考えよう.
この5桁の数は7つの素数をもつ最初の例である: 56003, 56113, 56333, 56443, 56663, 56773, 56993.
よって, この族の最初の数である56003は, このような性質を持つ最小の素数である.

桁を同じ数で置き換えることで8つの素数が得られる最小の素数を求めよ.
(注:連続した桁でなくても良い)

ソース

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

class Program
{
    //const int JyougenKeta = 2; const int NeedsCnt = 6;
    //const int JyougenKeta = 5; const int NeedsCnt = 7;
    const int JyougenKeta = 6; const int NeedsCnt = 8;

    static int[] SosuuArr = new int[(int)Math.Pow(10D, JyougenKeta) + 1];

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

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

    static List<string> PatternList = new List<string>();

    static void DerivePatternList()
    {
        foreach (char EachChar in "123456789*") {
            PatternList.Add(EachChar.ToString());
        }
        for (int Ketasuu = 2; Ketasuu <= JyougenKeta; Ketasuu++) {
            foreach (string EachStr in PatternList.FindAll(X => X.Length + 1 == Ketasuu)) {
                foreach (char EachChar in "0123456789*") {
                    PatternList.Add(EachStr + EachChar.ToString());
                }
            }
        }

        //少なくとも1つの*があるマッチパターンのみを抽出
        PatternList = PatternList.FindAll(X => X.Contains('*'));

        //末尾が*の場合は対象外(末尾が0,4,6,8は素数でなく、残りの数字の123579だと6通りしかないから)
        PatternList.RemoveAll(X => X.EndsWith("*"));

        //末尾が0,2,4,6,8は対象外(末尾が0,4,6,8は素数でなく、末尾が2の素数は1つしかない)
        PatternList.RemoveAll(X => X.EndsWith("0") || X.EndsWith("2") || X.EndsWith("4")
                                     || X.EndsWith("6") || X.EndsWith("8"));

        //*を0に変換して数値としてソートしておく (For文のBreakのため)
        PatternList = PatternList.OrderBy(X => int.Parse(X.Replace('*', '0'))).
            ThenBy(X => X.Length).ToList();
    }

    static void Main()
    {
        Eratosthenes();
        DerivePatternList();

        int AnswerMinStartSosuu = int.MaxValue;
        bool HasAnswerKouho = false;
        string AnswerPattern = "";
        string AnswerSosuuStrs = "";

        foreach (string EachPattern in PatternList) {
            Console.WriteLine("{0,6}をチェック中", EachPattern);

            if (HasAnswerKouho && int.Parse(EachPattern.Replace('*', '0')) > AnswerMinStartSosuu)
                break;

            var SosuuStrs = new System.Text.StringBuilder();
            int OKCnt = 0;
            int MinStartSosuu = int.MaxValue;

            const string SuutiArr = "0123456789";
            for (int I = 0; I <= SuutiArr.Length - 1; I++) {
                //先頭が*の場合の0は対象外
                if (EachPattern.StartsWith("*") && SuutiArr[I] == '0') continue;

                int WillSearchInt = int.Parse(EachPattern.Replace('*', SuutiArr[I]));
                if (Array.BinarySearch<int>(SosuuArr, WillSearchInt) >= 0) {
                    OKCnt++;
                    if (OKCnt == 1) MinStartSosuu = WillSearchInt;
                    SosuuStrs.AppendFormat("{0},", WillSearchInt.ToString());
                }
                int RestCnt = SuutiArr.Length - (I + 1);
                if (NeedsCnt - OKCnt > RestCnt) break; //試行回数不足
            }

            if (NeedsCnt <= OKCnt && MinStartSosuu < AnswerMinStartSosuu) {
                AnswerMinStartSosuu = MinStartSosuu;
                AnswerPattern = EachPattern;
                AnswerSosuuStrs = SosuuStrs.ToString();
                HasAnswerKouho = true;
            }
        }
        Console.WriteLine("パターンは{0}", AnswerPattern);
        Console.WriteLine("素数リストは{0}", AnswerSosuuStrs.ToString());
    }
}

実行結果

省略
1212*9をチェック中
1213*1をチェック中
1213*3をチェック中
1213*5をチェック中
1213*7をチェック中
1213*9をチェック中
1214*1をチェック中
パターンは*2*3*3
素数リストは121313,222323,323333,424343,525353,626363,828383,929393,

解説

パターンのListジェネリックに対して、FindAllやRemoveAllで余計な要素を削除してます。
そして、パターンごとに素数の配列に対して、複数回のバイナリサーチを行ってます。

MSDN --- List<T>.FindAll メソッド
MSDN --- List<T>.RemoveAll メソッド