Cマガ電脳クラブ(第031回) 小町素因数分解

問題

34504345 = 5 x 29 x 47 x 61 x 83
上の式は素因数分解である。ところが、この右辺には1〜9がすべて1字ずつ登場している。
ではこのように1〜9のすべての数字が1回ずつ登場するような素因数分解のうち、左辺の最小数を求めてください。

なお、ここにあげた34504345は最小ではない。
さらに、0〜9の10種の数字を含む場合はどうだろうか。
もちろん、0は各素数の左端にはこない。

ソース

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

class Program
{
    const int Jyougen = 16000000; //仮の上限
    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));

        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)
    {
        return Array.TrueForAll(pAppearedArr, X => X);
    }
}

実行結果

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

解候補を発見しました。
2*3*5*487*1069=15618090

解説

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

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