C#でプロジェクトオイラーを解く（問題４１「パンデジタル素数」）

Tweet

Pocket

どーも、みつおです。

出力の時間に30分くらいかかった。

改善の余地あり。。。

問題

n桁パンデジタルであるとは, 1からnまでの数を各桁に1つずつ持つこととする.

#下のリンク先にあるような数学的定義とは異なる

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

出典：Problem41

解答

using System;
using System.Linq;

namespace Problem41
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(Solve());
            Console.ReadLine();
        }

        private static long Solve()
        {
            long ret = 0;

            //９桁のパンデジタル数の最大値からループ
            for(long i = 987654321; i >= 1; i--)
            {
                //パンデジタル数か判定
                if(IsPandigital(i,i.ToString().Length))
                {
                    //素数か判定
                    if(IsSosu(i))
                    {
                        ret = i;
                        break;
                    }
                }
            }

            return ret;
        }

        private static bool IsPandigital(long no, int keta)
        {
            bool ret;
            string strketa = "";

            //文字列に変換
            string strdata = no.ToString();

            //パンデジタル数の並びを取得
            for (int i = 1; i <= keta; i++) strketa += i.ToString();

            //パンデジタル判定
            Predicate<string> IsPandigi = A => A.OrderBy(B => B).SequenceEqual(strketa);

            //文字の長さが同じかつ 数値が全て使われていればパンデジタル判定
            ret = strdata.Length == keta && IsPandigi(strdata.ToString());

            return ret;
        }

        private static bool IsSosu(long no)
        {
            bool ret = true;

            //数値が2未満（1)なら素数じゃない、2なら素数
            if (no < 2) return false;
            else if (no == 2) return true;

            //数値が2で割り切れるなら素数じゃない
            if (no % 2 == 0) return false;

            //合成数xはp≦√xを満たす素因子pをもつ
            double sqrtno = Math.Sqrt(no);

            //奇数でループ 
            for (int i = 3; i <= sqrtno; i += 2)
            {
                //割り切れるので素数じゃない
                if (no % i == 0) return false;
            }

            return ret;
        }
    }
}

出力

7652413