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

問題

3797は面白い性質を持っている. まずそれ自身が素数であり,
左から右に桁を除いたときに全て素数になっている(3797, 797, 97, 7).
同様に右から左に桁を除いたときも全て素数である(3797, 379, 37, 3).

右から切り詰めても左から切り詰めても素数になるような素数は11個しかない.総和を求めよ.

注: 2, 3, 5, 7を切り詰め可能な素数とは考えない.

ソース

using System;
using System.Linq;

class Program
{
    static int[] SosuuArr = new int[740001];

    //エラトステネスの篩
    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 void Main()
    {
        Eratosthenes();

        int SumVal = 0, Rest = 11;
        for (int I = 1; I <= SosuuArr.GetUpperBound(0); I++) {
            if (SosuuArr[I] < 10) continue;
            bool IsOK = true;
            for (int J = 10; J <= SosuuArr[I]; J *= 10) {
                if (Array.BinarySearch<int>(SosuuArr, SosuuArr[I] / J) < 0) {
                    IsOK = false; break;
                }
                if (Array.BinarySearch<int>(SosuuArr, SosuuArr[I] % J) < 0) {
                    IsOK = false; break;
                }
            }
            if (IsOK) {
                Console.WriteLine("{0,7},SumVal={1,7}", SosuuArr[I], SumVal += SosuuArr[I]);
                if (--Rest == 0) return;
            }
        }
    }
}

実行結果

     23,SumVal=     23
     37,SumVal=     60
     53,SumVal=    113
     73,SumVal=    186
    313,SumVal=    499
    317,SumVal=    816
    373,SumVal=   1189
    797,SumVal=   1986
   3137,SumVal=   5123
   3797,SumVal=   8920
 739397,SumVal= 748317

解説

型を変更しないように、10の乗数での剰余や商を求めてます。

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