メモリを節約して1000000番目の素数を求める

ハッシュテーブルのエントリ数は最大でも素数の個数で済んでいる。
（それでも、圧縮配列を使ったエラトステネスのふるいの方が優れているっぽい）

Program.cs

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        var sw = new Stopwatch();
        sw.Start();
        var p1000000 = Primes().Skip(999999).First();
        sw.Stop();
        Console.WriteLine(p1000000);
        Console.WriteLine(sw.Elapsed);
    }

    static IEnumerable<long> Primes()
    {
        yield return 2L;
        var composites = new CompositeTable();
        foreach (var i in OddsFrom3())
        {
            if (!composites.ContainsKey(i))
            {
                yield return i;
                var firstComposite = i * i;
                composites.Append(firstComposite, i);
            }
            else
            {
                foreach (var p in composites[i])
                {
                    var nextComposite = i + 2L * p;
                    composites.Append(nextComposite, p);
                }
                composites.Remove(i);
            }
        }
    }

    static IEnumerable<long> OddsFrom3()
    {
        for (var i = 3L; ; i += 2L) yield return i;
    }

    static IEnumerable<long> EnumerateFrom(long start)
    {
        while (true) yield return start++;
    }
}

class CompositeTable : Dictionary<long, List<long>>
{
    public void Append(long composite, long prime)
    {
        if (this.ContainsKey(composite))
            this[composite].Add(prime);
        else
            this[composite] = new List<long> { prime };
    }
}