Cマガ電脳クラブ(第090回) Primes in a Prime

問題

ここに8桁の素数がある。
　37673917
これは、逆に並べ換えても素数である。
　71937673
ここで、8桁を半分にして4桁ずつの2数に分けた場合、そのそれぞれもまた素数である。
　3767, 3917
さらに、それぞれの4桁を逆に並べてもこれまた素数になっている。
　7673, 7193
このような8桁の素数をほかに見つけてほしい。この例を含めて何通りあるだろうか。
もちろん、8桁を逆に並べたものは別の解とはしない。

ソース

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

class Program
{
    const int Jyougen = 99999999;
    static int[] SosuuArr;

    //エラトステネスの篩で上限以下の素数の配列を作成
    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 (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);
        }
        SosuuArr = SosuuList.ToArray();
    }

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

        Eratosthenes();

        int[] Sosuu4KetaArr =
            Array.FindAll(SosuuArr, X => 1000 <= X && X <= 9999);
        Sosuu4KetaArr =
            Array.FindAll(Sosuu4KetaArr, X => IsValidSaijyouiNum(X / 1000));

        int[] Sosuu8KetaArr =
            Array.FindAll(SosuuArr, X => 10000000 <= X && X <= 99999999);
        Sosuu8KetaArr =
            Array.FindAll(Sosuu8KetaArr, X => IsValidSaijyouiNum(X / 10000000));

        Console.WriteLine("4桁の候補な素数は{0}個", Sosuu4KetaArr.Length);
        Console.WriteLine("8桁の候補な素数は{0}個", Sosuu8KetaArr.Length);
        Console.WriteLine("経過時間={0}", sw.Elapsed);

        int AnswerCnt = 0;
        for (int I = 0; I <= Sosuu8KetaArr.GetUpperBound(0) - 1; I++) {
            int RevNum = DeriveRevNum(Sosuu8KetaArr[I]);
            int StaInd = I + 1;
            int wkInd = Array.BinarySearch(Sosuu8KetaArr, StaInd,
                Sosuu8KetaArr.Length - StaInd - 1, RevNum);
            if (wkInd < 0) continue;

            int Left4KetaNum, Right4KetaNum;
            Split8KetaNumArr(Sosuu8KetaArr[I], out Left4KetaNum, out Right4KetaNum);
            int RevLeft4KetaNum = DeriveRevNum(Left4KetaNum);
            int RevRight4KetaNum = DeriveRevNum(Right4KetaNum);

            if (Array.BinarySearch(Sosuu4KetaArr, Left4KetaNum) < 0
             || Array.BinarySearch(Sosuu4KetaArr, Right4KetaNum) < 0
             || Array.BinarySearch(Sosuu4KetaArr, RevLeft4KetaNum) < 0
             || Array.BinarySearch(Sosuu4KetaArr, RevRight4KetaNum) < 0)
                continue;

            AnswerCnt++;
            var sb = new System.Text.StringBuilder();
            sb.AppendFormat("解{0}を発見。", AnswerCnt);
            sb.AppendFormat("{0}で、反転は{1}。", Sosuu8KetaArr[I], RevNum);
            sb.AppendFormat("4桁の素数は、{0}と{1}と{2}と{3}。",
                Left4KetaNum, Right4KetaNum, RevLeft4KetaNum, RevRight4KetaNum);
            Console.WriteLine(sb.ToString());
        }
        Console.WriteLine("経過時間={0}", sw.Elapsed);
    }

    //指定した最上位桁の数字が2,4,5,6,8ならNG判定
    static bool IsValidSaijyouiNum(int pSaijyouiNum)
    {
        if (pSaijyouiNum == 2) return false;
        if (pSaijyouiNum == 4) return false;
        if (pSaijyouiNum == 5) return false;
        if (pSaijyouiNum == 6) return false;
        if (pSaijyouiNum == 8) return false;
        return true;
    }

    //数字を逆に並べた数値を返す
    static int DeriveRevNum(int pTargetNum)
    {
        int WillReturn = 0;
        foreach (int EachNum in DeriveExtractedNumArr(pTargetNum)) {
            WillReturn *= 10;
            WillReturn += EachNum;
        }
        return WillReturn;
    }

    //数字を下位桁から抽出した配列を返す
    static int[] DeriveExtractedNumArr(int pTargetNum)
    {
        int CopiedVal = pTargetNum;
        var WillReturn = new List<int>();

        do {
            WillReturn.Add(CopiedVal % 10);
            CopiedVal /= 10;
        } while (CopiedVal > 0);
        return WillReturn.ToArray();
    }

    //8桁を、4桁の数値2つに分割して返す
    static void Split8KetaNumArr(int pTargetNum,
        out int pLeft4KetaNum, out int pRight4KetaNum)
    {
        int[] ExtractedNum = DeriveExtractedNumArr(pTargetNum);
        int[] RevArr = ExtractedNum.Reverse().ToArray();

        Func<int, int, int> wkAct = (pFrom, pTo) =>
        {
            int SplitNum = 0;
            for (int I = pFrom; I <= pTo; I++) {
                SplitNum *= 10;
                SplitNum += RevArr[I];
            }
            return SplitNum;
        };
        pLeft4KetaNum = wkAct(0, 3);
        pRight4KetaNum = wkAct(4, 7);
    }
}

実行結果

省略
解485を発見。94973299で、反転は99237949。4桁の素数は、9497と3299と7949と9923。
解486を発見。95471669で、反転は96617459。4桁の素数は、9547と1669と7459と9661。
解487を発見。95479679で、反転は97697459。4桁の素数は、9547と9679と7459と9769。
解488を発見。96019769で、反転は96791069。4桁の素数は、9601と9769と1069と9679。
解489を発見。96131879で、反転は97813169。4桁の素数は、9613と1879と3169と9781。
解490を発見。96439769で、反転は96793469。4桁の素数は、9643と9769と3469と9679。
解491を発見。97211789で、反転は98711279。4桁の素数は、9721と1789と1279と9871。
解492を発見。97813889で、反転は98831879。4桁の素数は、9781と3889と1879と9883。
経過時間=00:00:39.0597941

解説

ナイーブに実装してます。