Cマガ電脳クラブ(第002回) ガンコ素数をさがせ！

問題

7193という数は素数であり、しかも右側からひとつずつ削っていっても、719, 71, 7 のようにすべて素数になる。
これを左ガンコ素数と呼ぶことにする。

6823 はそれ自身が素数であり、左から順に削った 823, 23, 3 が全部素数になる。これは右ガンコ素数だ。
さて問題。「左ガンコ素数であり、同時に右ガンコ素数である」最大の素数を見つけていただきたい。

ソース

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

class Program
{
    const int Jyougen = 9999999;
    static int[] SosuuArr = new int[Jyougen + 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 int[] DeriveStartArr()
    {
        var wkList = new List<int>(SosuuArr);

        //右端が1は、対象外
        wkList.RemoveAll(X => X % 10 == 1);

        //2桁以上で右端が9は、対象外
        wkList.RemoveAll(X => X >= 10 && X % 10 == 9);

        //2桁以上で左端が1,4,6,8,9は、対象外
        wkList.RemoveAll(X =>
        {
            string wkStr = X.ToString();
            return X >= 10 && (
                wkStr.StartsWith("1") || wkStr.StartsWith("4") || wkStr.StartsWith("6") ||
                wkStr.StartsWith("8") || wkStr.StartsWith("9"));
        });

        //0を含むと対象外
        wkList.RemoveAll(X => X.ToString().Contains('0'));

        return wkList.ToArray();
    }

    static void Main()
    {
        Console.WriteLine("{0}以下のガンコ素数を列挙します。", Jyougen);

        Eratosthenes();
        int[] StartArr = DeriveStartArr();

        foreach (var AnyInt in SosuuArr) {
            //1桁はガンコ素数
            if (AnyInt < 10) {
                Console.WriteLine("{0}はガンコ素数", AnyInt);
                continue;
            }

            bool IsOK = true;
            for (int I = 1; I <= DeriveKetasuu(AnyInt) - 1; I++) {
                int WK1 = AnyInt % CalcBekijyou(I);
                int WK2 = AnyInt / CalcBekijyou(I);

                if (Array.BinarySearch<int>(SosuuArr, WK1) < 0 ||
                    Array.BinarySearch<int>(SosuuArr, WK2) < 0) {
                    IsOK = false;
                    break;
                }
            }
            if (IsOK) Console.WriteLine("{0}はガンコ素数", AnyInt);
        }
    }

    static int DeriveKetasuu(int pTarget)
    {
        if (pTarget < 10) return 1;
        if (pTarget < 100) return 2;
        if (pTarget < 1000) return 3;
        if (pTarget < 10000) return 4;
        if (pTarget < 100000) return 5;
        if (pTarget < 1000000) return 6;
        return 7;
    }

    static int CalcBekijyou(int pJyousuu)
    {
        int WillReturn = 1;
        for (int I = 1; I <= pJyousuu; I++) {
            WillReturn *= 10;
        }
        return WillReturn;
    }
}

実行結果

9999999以下のガンコ素数を列挙します。
2はガンコ素数
3はガンコ素数
5はガンコ素数
7はガンコ素数
23はガンコ素数
37はガンコ素数
53はガンコ素数
73はガンコ素数
313はガンコ素数
317はガンコ素数
373はガンコ素数
797はガンコ素数
3137はガンコ素数
3797はガンコ素数
739397はガンコ素数

解説

9999999以下のガンコ素数を列挙して、最大のガンコ素数が
 739397でしたので、最大の素数を見つけるという題意を満たしてます。

Problem37 切り詰めても素数になる数の総和