CODE:

//ｎ番目素数を求めるプログラム　№4
//エラトステネスのふるい改良版
//Compile:
//C:\windows\microsoft.net\framework\v4.0.30319\csc.exe Prime4.cs
//使い方：
// Prime4 <n>（複数指定可）
//

using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;

namespace Prime4
{
    class Program
    {
        static void Main(string[] args)
        {
            TextWriterTraceListener tl =
				new TextWriterTraceListener(System.IO.File.CreateText("debug.txt"));
            Debug.Listeners.Clear();
            Debug.Listeners.Add(tl);

            foreach (string arg in args)
            {
                int num;
                if (!int.TryParse(arg, out num))
                {
                    continue;
                }
                DateTime dtBegin;
                int n;
                dtBegin = DateTime.Now;
                n = 0;
                foreach (int p in Prime())
                {
                    ++n;
                    //Console.WriteLine(string.Format("{0}:{1}", n, p));
                    if (n == num)
                    {
                        Console.WriteLine(string.Format("{0}番目の素数:{1}", n, p));
                        break;
                    }
                }
                Console.WriteLine(
					string.Format("計算時間：{0,8:#0.###}秒"
						, (DateTime.Now - dtBegin).Ticks / 10000000.0));
            }

            Console.WriteLine(
				string.Format("使用メモリサイズ：{0}MB"
					, Environment.WorkingSet / 1000 / 1000));
            Debug.Flush();
        }

        static List<int> aPrime = new List<int>();
        public static IEnumerable<int> Prime()
        {
            // 最初の素数
            if (aPrime.Count == 0)
            {
                aPrime.Add(2);
                aPrime.Add(3);
            }
            // 作成済み素数出力／新しい素数を見つけるための情報を取得
            int next_x = aPrime[aPrime.Count - 1] + 2;  // 新しい素数候補
            int sieve_prime_order = 0;  // ふるいを作るための最大素数の順位
            int out_order;  // 出力済み素数順位
            for (out_order = 0; out_order < aPrime.Count; ++out_order)
            {
                yield return aPrime[out_order];
                if (aPrime[out_order] * aPrime[out_order] < next_x)
                {
                    sieve_prime_order = out_order;
                }
            }
            int sieve_from = aPrime[sieve_prime_order] * aPrime[sieve_prime_order]; // ふるいの最小値
            ++sieve_prime_order;
            int sieve_to = aPrime[sieve_prime_order] * aPrime[sieve_prime_order];   // ふるいの最大値
            int sieve_prime = aPrime[sieve_prime_order];    // ふるいを作るための最大素数
            // 新しい素数を探す
            while (true)
            {
                int sieve_size = sieve_to - sieve_from; // ふるいサイズ
                bool[] ab = new bool[sieve_size];   // ふるい（false:素因数なし true:素因数あり）
                // sieve_prime 以下の全ての素数について、ふるい中のその素数の倍数に true を設定する
                foreach (int p in aPrime)
                {
                    for (int x = (p - (sieve_from % p)); x < sieve_size; x += p)
                    {
                        ab[x] = true;
                    }
                    if (p == sieve_prime)
                    {
                        break;
                    }
                }
                // ふるいの中の false となっている全ての値を素数として出力する
                for (int i = next_x - sieve_from; i < sieve_size; ++i)
                {
                    if (!ab[i])
                    {
                        aPrime.Add(sieve_from + i);
                        yield return sieve_from + i;
                    }
                }
                // ふるいを作成するための素数を１つ追加して情報を更新する
                sieve_from = sieve_to;
                ++sieve_prime_order;
                sieve_to = aPrime[sieve_prime_order] * aPrime[sieve_prime_order];
                sieve_prime = aPrime[sieve_prime_order];
                next_x = sieve_from + 2;
            }
        }
    }
}