Cマガ電脳クラブ(第097回) 昇順素数

問題

2､3､5､7､11､13は素数だ｡
でもここでは素数の各桁を構成する数字が、右に行くに従って大きくなるもの、つまり昇順素数だけを考えたい。
とすると13には資格があるが､11は失格する｡ひと桁の素数はすべて昇順素数であるとする｡

さて、ある異なる三つの昇順素数を足し合わせたところ、その結果も昇順素数になっていたという。
 19+89+359=467
このような3数の組はこの例を含めて何通りあるだろうか｡

ソース

using System;
using System.Collections.Generic;

class Program
{
    const int Jyougen = 123456789;
    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();
        Console.WriteLine("{0}以下の素数は{1}個", Jyougen, SosuuArr.Length);

        int[] AscSosuuArr = Array.FindAll(SosuuArr, X => IsAscSosuu(X));
        Console.WriteLine("{0}以下の昇順素数は{1}個", Jyougen, AscSosuuArr.Length);

        int AnswerCnt = 0;
        for (int I = 0; I <= AscSosuuArr.GetUpperBound(0); I++) {
            for (int J = I + 1; J <= AscSosuuArr.GetUpperBound(0); J++) {
                for (int K = J + 1; K <= AscSosuuArr.GetUpperBound(0); K++) {
                    int wkSum = AscSosuuArr[I] + AscSosuuArr[J] + AscSosuuArr[K];

                    int StaInd = K + 1;
                    int wkInd =
                        Array.BinarySearch(AscSosuuArr, StaInd, AscSosuuArr.Length - StaInd, wkSum);
                    if (wkInd >= 0) {
                        Console.WriteLine("解{0}を発見。{1}+{2}+{3}={4}",
                            ++AnswerCnt, AscSosuuArr[I], AscSosuuArr[J], AscSosuuArr[K], wkSum);
                    }
                }
            }
        }
        Console.WriteLine("経過時間={0}", sw.Elapsed);
    }

    //昇順素数かを判定
    static bool IsAscSosuu(int pTarget)
    {
        var NumList = new List<int>();
        int CopiedVal = pTarget;

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

        NumList.Reverse();
        for (int I = 0; I <= NumList.Count - 1 - 1; I++) {
            if (NumList[I] >= NumList[I + 1])
                return false;
        }
        return true;
    }
}

実行結果

解290を発見。389+479+12589=13457
解291を発見。389+1279+1789=3457
解292を発見。389+1289+1789=3467
解293を発見。389+1489+1579=3457
解294を発見。389+1489+2689=4567
解295を発見。389+1789+2389=4567
解296を発見。1289+1489+1789=4567
経過時間=00:00:41.0077973

解説

エラトステネスの篩で123456789以下の素数を列挙してから、
昇順素数かを判定してます。

深さ優先探索を使って、
2の9乗-1= 511通りの
昇順な数を列挙してから、試し割りで素数判定したほうが
高速に処理できそうですね。