Pongeponge

読者です 読者をやめる 読者になる 読者になる

Project Euler : Problem 7 『10001st prime』

LEGO Police 逮捕!LEGO Police 逮捕! / Norio.NAKAYAMA
projecteuler.net


問題

 10001個目の素数は何や。


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

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


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


判別手順

 n番の罪人が来た場合、

  1. 2の倍数は即釈放(というか来ない)
  2. 既に入ってる囚人番号(素数)を小さい順に使って、nの試し割りをする
  3. ルートn以上の囚人番号で試し割りをする必要はない
  4. 試し割りで割り切れたら釈放
  5. どの囚人番号でも割り切れなかったら、n番は今日から囚人生活
  6. どんどん判別していって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;
        }
    }
}
解答

104743



素因数分解と素数判定

素因数分解と素数判定

  • 作者: デヴィッド・M.ブレッソード,David M. Bressoud,玉井浩
  • 出版社/メーカー: エスアイビーアクセス
  • 発売日: 2004/03
  • メディア: 単行本
  • クリック: 26回
  • この商品を含むブログ (5件) を見る
素数表150000個

素数表150000個