Problem118 パンデジタル素数集合

問題

1から9の全ての数字を使い, 自由につなげることで
10進数の数字を作り,複数の集合を作ることができる.

集合 {2,5,47,89,631} は面白いことに全ての要素が素数である.

1から9の数字をちょうど1個ずつ含み,
素数の要素しか含まない集合はいくつあるか?

ソース

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

class Program
{
    const int Jyougen = 98765432;
    //const int Jyougen = 631;

    static string[] StrSosuuArr;

    //エラトステネスの篩
    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 (I != 2 && I % 2 == 0) continue;

            if (IsSosuuArr[I]) {
                for (int J = I * 2; J <= IsSosuuArr.Count - 1; J += I) {
                    IsSosuuArr[J] = false;
                }
            }
        }
        var StrSosuuList = new List<string>();
        for (int I = 2; I <= IsSosuuArr.Count - 1; I++)
            if (IsSosuuArr[I]) StrSosuuList.Add(I.ToString());

        //0を含む場合は、対象外
        StrSosuuList.RemoveAll(X => X.Contains('0'));

        //同じ数字を複数含んだ場合は、対象外
        StrSosuuList.RemoveAll(X => HasDuplicate(X));

        //8桁で、2と3と5と7を含んだら対象外(1,4,6,8,9は素数でないため)
        StrSosuuList.RemoveAll(X =>
        {
            if (X.Length != 8) return false;
            if (X.Contains('2') && X.Contains('3')
             && X.Contains('5') && X.Contains('7')) return true;
            return false;
        });

        //987654321は
        //8+7=15 で 5+4=9 で2+1=3 なので、3の倍数であり、素数ではない
        //よって、987654321(数字を入れ替えた数を含む)の考慮は不要

        StrSosuuArr = StrSosuuList.ToArray();
    }

    static bool HasDuplicate(string pStr)
    {
        var wkSet = new HashSet<char>();
        foreach (var EachChar in pStr) {
            if (wkSet.Add(EachChar) == false)
                return true;
        }
        return false;
    }

    struct JyoutaiDef
    {
        internal int CurrP;
        internal string Path;
    }

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

        Console.WriteLine("エラトステネスの篩を実行中");
        Eratosthenes();

        Console.WriteLine("深さ優先探索を実行中");
        var Stk = new Stack<JyoutaiDef>();

        JyoutaiDef WillPush;
        for (int I = 0; I <= StrSosuuArr.GetUpperBound(0); I++) {
            //昇順で素数の組み合わせを列挙するので、4桁を超えたらBreak
            if (StrSosuuArr[I].Length > 4) break;

            WillPush.CurrP = I;
            WillPush.Path = StrSosuuArr[I].ToString();
            Stk.Push(WillPush);
        }

        int AnswerCnt = 0;
        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();

            char[] SortedArr = Popped.Path.Where(X => X != ',').OrderBy(X => X).ToArray();

            if (SortedArr.SequenceEqual("123456789")) {
                AnswerCnt++;
                Console.WriteLine("{0}。Answer{1}。{2}", sw.Elapsed, AnswerCnt, Popped.Path);
                continue;
            }

            for (int I = Popped.CurrP + 1; I <= StrSosuuArr.GetUpperBound(0); I++) {
                if (SortedArr.Length + StrSosuuArr[I].Length > 9) break;
                if (SortedArr.Intersect(StrSosuuArr[I]).Any()) continue;

                WillPush.CurrP = I;
                WillPush.Path = Popped.Path + "," + StrSosuuArr[I].ToString();
                Stk.Push(WillPush);
            }
        }
    }
}

実行結果

省略
00:00:58.3596577。Answer44668。2,3,5,7,84961
00:00:58.3597300。Answer44669。2,3,5,7,84691
00:00:58.3597960。Answer44670。2,3,5,7,81649
00:00:58.3598608。Answer44671。2,3,5,7,69481
00:00:58.3599256。Answer44672。2,3,5,7,68491
00:00:58.3599898。Answer44673。2,3,5,7,64891
00:00:58.3600546。Answer44674。2,3,5,7,64189
00:00:58.3601262。Answer44675。2,3,5,7,49681
00:00:58.3601901。Answer44676。2,3,5,7,48619
00:00:58.3602547。Answer44677。2,3,5,7,46819
00:00:58.3603192。Answer44678。2,3,5,7,14869
00:00:58.3608458。Answer44679。2,3,5,7,89,641
00:00:58.3609285。Answer44680。2,3,5,7,89,461

解説

ListジェネリックのRemoveAllメソッドで、余計な要素を削除してます。

MSDN --- List<T>.RemoveAll メソッド