Problem60 任意の2つの素数を繋げても素数な、5つの素数の組

問題

素数3, 7, 109, 673は非凡な性質を持っている.
任意の2つの素数を任意の順で繋げると, また素数になっている.

例えば, 7と109を用いると, 7109と1097の両方が素数である.
これら4つの素数の和は792である.
これは, このような性質をもつ4つの素数の組の和の中で最小である.

任意の2つの素数を繋げたときに別の素数が生成される, 5つの素数の組の和の中で最小のものを求めよ.

ソース

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

class Program
{
    //const int CombinationCnt = 4;
    //const int Jyougen = 800;
    const int CombinationCnt = 5;
    const int Jyougen = 27000;

    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).OrderByDescending(X => X).ToArray();
    }

    struct JyoutaiDef
    {
        internal List<int> ValList;
        internal string Path;
    }

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

        Eratosthenes();

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        foreach (int Each in SosuuArr) {
            WillPush.ValList = new List<int> { Each };
            WillPush.Path = Each.ToString() + ",";
            Stk.Push(WillPush);
        }

        string AnswerPath = "";
        int AnswerSumMin = Jyougen;

        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();
            Console.WriteLine("{0} Path={1} 解候補={2}", sw.Elapsed, Popped.Path, AnswerPath);

            int wkSum = Popped.ValList.Sum();

            if (Popped.ValList.Count == CombinationCnt && wkSum < AnswerSumMin) {
                AnswerSumMin = wkSum;
                AnswerPath = Popped.Path;
                continue;
            }

            int ValCnt = Popped.ValList.Count;
            int RestCnt = CombinationCnt - ValCnt;

            int LastVal = Popped.ValList[ValCnt - 1];
            foreach (int Each in SosuuArr.Where(X => X > LastVal
                                             && AnswerSumMin > wkSum + X * RestCnt)) {
                bool wkBool;
                wkBool = Popped.ValList.TrueForAll(X => IsSosuu(DeriveConcatVal(X, Each)));
                if (wkBool == false) continue;
                wkBool = Popped.ValList.TrueForAll(X => IsSosuu(DeriveConcatVal(Each, X)));
                if (wkBool == false) continue;

                WillPush.ValList = new List<int>(Popped.ValList);
                WillPush.ValList.Add(Each);
                WillPush.Path = Popped.Path + Each.ToString() + ",";
                Stk.Push(WillPush);
            }
        }
        Console.WriteLine("{0}以下の素数の組み合わせで検証しました。", Jyougen);
        Console.WriteLine("解は{0}で和は{1}です。", AnswerPath, AnswerSumMin);
    }

    static bool IsSosuu(long pVal)
    {
        if (pVal <= Jyougen) return SosuuArr.Contains((int)pVal);

        if (pVal % 2 == 0) return false;
        for (int I = 3; I * I <= pVal; I += 2) {
            if (pVal % I == 0) return false;
        }
        return true;
    }

    static long DeriveConcatVal(int pLeft, int pRight)
    {
        //return long.Parse(pLeft.ToString() + pRight.ToString()); のちょっとだけ速度改善
        long WillReturn = pLeft;
        if (pRight < 10) WillReturn *= 10; //1桁の場合
        else if (pRight < 100) WillReturn *= 100; //2桁の場合
        else if (pRight < 1000) WillReturn *= 1000; //3桁の場合
        else if (pRight < 10000) WillReturn *= 10000; //4桁の場合
        else if (pRight < 100000) WillReturn *= 100000; //5桁の場合

        WillReturn += pRight;
        return WillReturn;
    }
}

実行結果

省略
00:00:12.7278866 Path=26953, 解候補=13,5197,5701,6733,8389,
00:00:12.7279056 Path=26959, 解候補=13,5197,5701,6733,8389,
00:00:12.7279282 Path=26981, 解候補=13,5197,5701,6733,8389,
00:00:12.7279623 Path=26987, 解候補=13,5197,5701,6733,8389,
00:00:12.7279847 Path=26993, 解候補=13,5197,5701,6733,8389,
27000以下の素数の組み合わせで検証しました。
解は13,5197,5701,6733,8389,で和は26033です。

解説

深さ優先探索で早く解候補を求めて、枝切り条件に使用してます。

枝切りでは、
素数の昇順になる組み合わせでチェックしているので
解候補の和を超える素数の組み合わせを枝切りしてます。

素数の和の上限を27000と仮決めした上で、
27000以下の素数の組み合わせで検証して
求まった解の合計が26033で
27000 > 26033 なので、5つの素数の組の和の中で最小のものという題意を満たしてます :-)
反復深化で素数の上限を増やしていくほうが、
解答としては優れているかもしれません :-)