C#でプロジェクトオイラーを解く（問題７「10001番目の素数」）

Tweet

Pocket

どーも、みつおです。

素数を判定するプログラムを間違えて、かなり実行速度が遅くなって焦った。

問題

素数を小さい方から6つ並べると 2, 3, 5, 7, 11, 13 であり, 6番目の素数は 13 である.

10 001 番目の素数を求めよ.

出典：Problem7

解答

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

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

        private static int Solve()
        {
            int ret = 0;
            int sosuNo = 0;

            //素数が10001番目になるまでループ
            while (sosuNo != 10001)
            {
                //素数判定する値をインクリメント
                ret++;

                //素数判定
                if (IsSosu(ret)) sosuNo++;
            }
            
            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;

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

            return ret;
        }
    }
}

出力

104743