Cマガ電脳クラブ(第122回) 3型素組数

問題

619737131179
この数は、なかからどの並んだ2桁の数をとっても素数になっており、しかもすべて異なっている。
このような数を2型素組数と呼ぶことにする。実はこの数は最大の2型素組数である。

では，3型素組数 (並んだ3桁のどれもが相異なる素数となっている数) の最大を見つけてほしい。
また、その最大値と同じ桁数には何個の3型素組数があるだろうか。

ソース

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

class Program
{
    const int Jyougen = 999;
    static string[] SosuuStrArr;

    //エラトステネスの篩
    static void Eratosthenes(int pKetasuu)
    {
        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 (IsSosuuArr[I] == false) continue;
            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);
        }
        var wkList = SosuuList.ConvertAll(X => X.ToString());
        wkList.RemoveAll(X => X.Length > pKetasuu);
        SosuuStrArr = wkList.Select(X => X.PadLeft(pKetasuu, '0')).ToArray();
    }

    static void Main()
    {
        var sw = System.Diagnostics.Stopwatch.StartNew();
        Solve(2);
        Solve(3);
        Console.WriteLine("経過時間={0}", sw.Elapsed);
    }

    struct JyoutaiDef
    {
        internal string NumStr;
    }

    static void Solve(int pN)
    {
        Eratosthenes(pN);
        var NSokumisuuList = new List<string>();

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        foreach (string EachStr in SosuuStrArr) {
            WillPush.NumStr = EachStr;
            stk.Push(WillPush);
        }

        int MaxNumLen = int.MinValue;
        while (stk.Count > 0) {
            JyoutaiDef Popped = stk.Pop();

            int NumLen = Popped.NumStr.TrimStart('0').Length;

            if (MaxNumLen < NumLen) {
                MaxNumLen = NumLen;
                NSokumisuuList.Clear();
            }
            if (MaxNumLen == NumLen)
                NSokumisuuList.Add(Popped.NumStr);

            for (char I = '0'; I <= '9'; I++) {
                WillPush.NumStr = Popped.NumStr + I.ToString();
                int FromInd = WillPush.NumStr.Length - pN;
                string wkStr = WillPush.NumStr.Substring(FromInd);
                if (Array.BinarySearch(SosuuStrArr, wkStr) < 0) continue;
                if (Popped.NumStr.Contains(wkStr)) continue;

                stk.Push(WillPush);
            }
        }
        string MaxNSokumisuu = NSokumisuuList.Max();
        Console.WriteLine("最大の{0}型組素数={1}", pN, MaxNSokumisuu);
        Console.WriteLine("桁数={0}。同じ桁での個数={1}",
            MaxNSokumisuu.Length, NSokumisuuList.Count);
        Console.WriteLine();
    }
}

実行結果

最大の2型組素数=619737131179
桁数=12。同じ桁での個数=192

最大の3型組素数=9419919379773971911373313179
桁数=28。同じ桁での個数=2860

経過時間=00:00:41.3486121

解説

深さ優先探索で順列を全探索してます。