Problem41 素数の中で最大のn桁Pandigital数

問題

n桁Pandigitalであるとは, 1からnまでの数を各桁に1つずつ持つこととする.

例えば2143は4桁Pandigital数であり, かつ素数である.
n桁（この問題の定義では9桁以下）Pandigitalな素数の中で最大の数を答えよ.

ソース

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        int MaxAnswer = int.MinValue;
        const string StrKouho = "123456789";
        var Stk = new Stack<string>();

        for (int I = 0; I <= StrKouho.Length - 1; I++) {
            Stk.Push(StrKouho[I].ToString());
        }

        while (Stk.Count > 0) {
            string Popped = Stk.Pop();

            bool IsPandigital = true;
            for (int I = 1; I <= Popped.Length; I++) {
                if (Popped.Contains(I.ToString()) == false) {
                    IsPandigital = false;
                    break;
                }
            }

            bool IsSosuu = true;
            int wkParsed = int.Parse(Popped);
            if (IsPandigital) {
                for (int I = 2; I * I <= wkParsed; I++) {
                    if (wkParsed % I == 0) {
                        IsSosuu = false;
                        break;
                    }
                }
            }
            if (IsPandigital && IsSosuu) {
                if (MaxAnswer < wkParsed) {
                    Console.WriteLine(Popped);
                    MaxAnswer = wkParsed;
                }
            }

            for (int I = 0; I <= StrKouho.Length - 1; I++) {
                if (Popped.Contains(StrKouho[I].ToString()) == false) {
                    string WillPush = Popped + StrKouho[I].ToString();
                    Stk.Push(WillPush);
                }
            }
        }
    }
}

実行結果

7652413

解説

深さ優先探索で、枝切りしながら、組み合わせを列挙してます。