C#でプロジェクトオイラーを解く（問題３５「巡回素数」）

Tweet

Pocket

どーも、みつおです。

問題

197は巡回素数と呼ばれる. 桁を回転させたときに得られる数 197, 971, 719 が全て素数だからである.

100未満には巡回素数が13個ある: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, および97である.

100万未満の巡回素数はいくつあるか?

出典：Problem35

解答

using System;
using System.Collections.Generic;

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

        private static int Solve()
        {
            int ret = 0;
            int limit = 1000000;
            List<int> sosulist = new List<int>();

            //素数のリストを作成
            for (int i = 2; i < limit; i++)
            {
                if (IsSosu(i)) sosulist.Add(i);
            }

            //素数の数分ループ
            foreach(var sosu in sosulist)
            {
                //巡回素数か判定　巡回数であればカウントアップ
                if (IsZyunkaiSosu(sosu, sosulist)) ret++;
            }

            return ret;
        }

        private static bool IsZyunkaiSosu(int no, List<int> sosulist)
        {
            bool ret = true;
            int syou = 0;                                            //商
            int amari = 0;                                           //余り
            int keta = (int)Math.Pow(10, no.ToString().Length - 1);  //最上位の桁を取得するための値
            int num = no;                                            //巡回数（数値）
            string strnum = "";                                      //巡回数（文字列）

            //桁数分ループ
            for(int i = 1;i < no.ToString().Length; i++)
            {
                //商と余りを取得
                syou = num / keta;
                amari = num % keta;

                //最上位を最下位に移動（数値を巡回）
                strnum = amari.ToString() + syou.ToString();

                //文字列を数値に変換
                num = Convert.ToInt32(strnum);

                //素数リストに巡回数があるか判定　巡回数でなければfalseを返す
                var find = sosulist.Find(tmp => tmp == num);
                if (find < 1) return false;
            }

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

出力

55