Cマガ電脳クラブ(第011回) 最小の素数？

問題

次の式を見ると、左辺はすべて素数で、素因数分解になっている。
左辺をもっとよく見ると、1〜9の数字を1度ずつすべて使って組み合わせてある。

2 × 7 × 853 × 6491 = 77515522

ここで問題。上の例のように、
「1〜9の9個の数字を1度ずつすべて使って組み合わせて作った素数の積」が最小になる組み合わせを求めてほしい。
例では4個の素数の積になっているが、何個の積でもよい。ちなみに"1"は素数ではない。

ついでにもう1問。
「1〜9の9個」ではなくて、
「0〜9の10個」ではどうなるだろうか。ただし、0は各素数の最上位桁にはできない。

ソース

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

class Program
{
    const int Jyougen = 3000000; //仮の上限
    static List<int> SosuuList;

    //エラトステネスの篩
    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;
            }
        }
        SosuuList = new List<int>();
        for (int I = 2; I <= IsSosuuArr.Count - 1; I++) {
            if (IsSosuuArr[I]) SosuuList.Add(I);
        }
    }

    struct JyoutaiDef
    {
        internal int CurrP;
        internal int ProdVal;
        internal bool[] AppearedArr;
        internal string Path;
    }

    static void Main()
    {
        Eratosthenes();

        //同じ数字が2つ以上あったらRemove
        Predicate<int> HasDuplicateInNum = pTarget =>
        {
            int[] AppearCntArr = new int[10 + 1];
            do {
                int wkInt = pTarget % 10;
                if (++AppearCntArr[wkInt] == 2) return true;
            } while ((pTarget /= 10) > 0);
            return false;
        };
        SosuuList.RemoveAll(X => HasDuplicateInNum(X));

        //ゼロを含んだらRemove
        Predicate<int> HasZeroInNum = pTarget =>
        {
            do {
                if (pTarget % 10 == 0) return true;
            } while ((pTarget /= 10) > 0);
            return false;
        };
        SosuuList.RemoveAll(X => HasZeroInNum(X));

        Console.WriteLine("{0}以下の素数で、", Jyougen);
        Console.WriteLine("積が{0}以下となる組み合わせを検証します。", Jyougen);
        Console.WriteLine("{0}以下の素数の最大値は{1}です。", Jyougen, SosuuList.Max());
        Console.WriteLine();

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;

        for (int P = 0; P <= SosuuList.Count - 1; P++) {
            WillPush.CurrP = P;
            WillPush.ProdVal = SosuuList[P];
            WillPush.AppearedArr = new bool[10];
            FillAppearedArr(SosuuList[P], WillPush.AppearedArr);
            WillPush.Path = SosuuList[P].ToString();
            stk.Push(WillPush);
        }

        int AnswerVal = Jyougen;

        while (stk.Count > 0) {
            JyoutaiDef Popped = stk.Pop();

            if (AnswerVal < Popped.ProdVal) continue;

            if (HasAllNumber(Popped.AppearedArr)) {
                Console.WriteLine("解候補を発見しました。");
                Console.WriteLine("{0}={1}", Popped.Path, Popped.ProdVal);
                AnswerVal = Popped.ProdVal;
                continue;
            }

            for (int P = Popped.CurrP + 1; P <= SosuuList.Count - 1; P++) {
                WillPush.CurrP = P;

                long wkLongProd = (long)Popped.ProdVal * SosuuList[P];
                if (AnswerVal < wkLongProd) break;
                WillPush.ProdVal = (int)wkLongProd;

                WillPush.AppearedArr = (bool[])Popped.AppearedArr.Clone();
                if (FillAppearedArr(SosuuList[P], WillPush.AppearedArr) == false)
                    continue;
                WillPush.Path = Popped.Path + "*" + SosuuList[P].ToString();
                stk.Push(WillPush);
            }
        }
    }

    //登場した数字を添字として配列値にTrueをセット
    //配列値が既にTrue(数字が登場済)であれば、FalseをReturn
    static bool FillAppearedArr(int pTarget, bool[] pAppearedArr)
    {
        do {
            int wkInt = pTarget % 10;
            if (pAppearedArr[wkInt]) return false;
            pAppearedArr[wkInt] = true;
        } while ((pTarget /= 10) > 0);
        return true;
    }

    //配列が、数字を全て含むかを判定
    static bool HasAllNumber(bool[] pAppearedArr)
    {
        for (int I = 1; I <= 9; I++) {
            if (pAppearedArr[I] == false) return false;
        }
        return true;
    }
}

実行結果

3000000以下の素数で、
積が3000000以下となる組み合わせを検証します。
3000000以下の素数の最大値は2987651です。

解候補を発見しました。
2*3*5*67*1489=2992890

解説

掛け算でInt型の最大値を超える可能性がある箇所のみで、Int型からLong型にキャストしてます。

0から9での答えは、第031回 小町素因数分解で扱ってます。
(第011回と第031回は、同じ問題であるため)