Project Euler : Problem 7 『10001st prime』

LEGO Police 逮捕！ / Norio.NAKAYAMA

projecteuler.net

問題

　10001個目の素数は何や。

素数、好き過ぎるやろ……

　ダイレクトに「何個目の素数は？」と求めることはできない。
なので、素数を入れる10001個の箱を用意して、小さい順に埋めていけばいい。
一番最後に入れられた数が10001個目の素数。

　イメージとしては、番号が書かれた罪人を、素数なら牢獄それ以外は釈放、という風に選別する感じ。

判別手順

　n番の罪人が来た場合、

2の倍数は即釈放(というか来ない)
既に入ってる囚人番号(素数)を小さい順に使って、nの試し割りをする
ルートn以上の囚人番号で試し割りをする必要はない
試し割りで割り切れたら釈放
どの囚人番号でも割り切れなかったら、n番は今日から囚人生活
どんどん判別していって10001個目の牢獄が埋まれば、そこに入ってる囚人番号を見る

　罪深い。

コード

using System;
using System.Diagnostics;

namespace Problem7
{
    class Program
    {
        static void Main(string[] args)
        {
            Int64 n = 10001;

            Debug.WriteLine(Prime(n));
        }

        static Int64 Prime(Int64 n)
        {
            Int64[] primeList = new Int64[n];
            primeList[0] = 2;

            Int64 num = 3;

            int count = 1;
            while (primeList[primeList.Length - 1] == 0)
            {
                if (IsPrime(num, primeList) == true)
                {
                    primeList[count] = num;
                    count++;
                }
                num += 2;
            }

            return primeList[n - 1];
        }


        //素数判定
        static bool IsPrime(Int64 n, Int64[] pl)
        {
            Int64 sqrtNum = (Int64)Math.Sqrt(n);

            for (int i = 0; pl[i] != 0; i++)
            {
                if ((n % pl[i] == 0) & (pl[i] <= sqrtNum))
                {
                    return false;
                }
            }

            return true;
        }
    }
}