C#でプロジェクトオイラーを解く（問題３７「切り詰め可能素数」）

Tweet

Pocket

どーも、みつおです。

問題

3797は面白い性質を持っている. まずそれ自身が素数であり, 左から右に桁を除いたときに全て素数になっている (3797, 797, 97, 7). 同様に右から左に桁を除いたときも全て素数である (3797, 379, 37, 3).

右から切り詰めても左から切り詰めても素数になるような素数は11個しかない. 総和を求めよ.

注: 2, 3, 5, 7を切り詰め可能な素数とは考えない.

出典：Problem37

解答

using System;

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


        private static int Solve()
        {
            int ret = 0;
            int limit = 11;
            int cnt = 0;
            int i = 0;

            //切り詰め可能素数が１１になるまでループ
            while(cnt != limit)
            {
                i++;
                //素数判定
                if(IsSosu(i))
                {
                    //切り詰め素数判定
                    if (IsKiritsumeSosu(i))
                    {
                        ret = ret + i;
                        cnt++;
                    }
                }
            }

            return ret;
        }

        private static bool IsKiritsumeSosu(int no)
        {
            bool ret = true;
            int syou = no;                                            //商
            int amari = no;                                           //余り
            int keta = (int)Math.Pow(10, no.ToString().Length - 1);  //最上位の桁を取得するための値

            //1桁は切り詰め可能素数と数えない
            if (no.ToString().Length == 1) return false;

            #region 左から右で素数判定
            //桁数分ループ
            for (int i = 1; i < no.ToString().Length; i++)
            {
                //余りを取得
                amari = amari % keta;

                //素数じゃなければfalseを返す
                if (!IsSosu(amari)) return false;
                else keta /= 10;
            }
            #endregion
            
            keta = (int)Math.Pow(10, no.ToString().Length - 1);  //最上位の桁を取得するための値

            #region 右から左で素数判定
            //桁数分ループ
            for (int i = 1; i < no.ToString().Length; i++)
            {
                //商を取得
                syou = no / keta;

                //素数じゃなければfalseを返す
                if (!IsSosu(syou)) return false;
                else keta /= 10;
            }
            #endregion


            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;
        }
    }
}

出力

748317