素数をひたすら列挙し続けるイテレータブロック

はてブのホットエントリで素数ネタが話題になってたので、何となく作ってみました。

yield returnを用いると、自分でIenumerableな形のシーケンスを生成することができます。
ということで、素数を延々と列挙し続けるシーケンスを作ってみました。
無限のシーケンスを生成するので、foreachに入れたり、LINQのCountみたいな即時評価するメソッドに渡すと無限ループに陥ります。
指定の数まで取り出したい時は、Takeメソッドとかでシーケンスを加工すればOK!!

1000番目の素数までを列挙

            foreach (var i in GetPrimeNumbers().Take(1000-1))
            {
                Console.WriteLine(i);
            }

素数をひたすら列挙し続ける

        static void Main(string[] args)
        {
            foreach (var i in GetPrimeNumbers())
            {
                Console.WriteLine(i);
            }
        }

        static IEnumerable<BigInteger> GetPrimeNumbers()
        {
            BigInteger candidate = 2;
            yield return 2; // 2は素数

            while (true)
            {
                if (IsPrimeNumbers(candidate))
                    yield return candidate;
                candidate++;
            }
        }

        static bool IsPrimeNumbers(BigInteger v)
        {
            if (v % 2 == 0)
                return false;

            // ↓のループ条件「i <= v /i」は、 「i <= sqrt(v)」 と同じ
            // 「i <= sqrt(v)」⇒「pow(i) <= v」⇒「i <= v /i」
            // BigIntegerはsqrtないし、ルートの計算するの大変だから。
            for (BigInteger i = 3; i <= v / i; i+=2)
            {
                if (v % i == 0)
                    return false;
            }
            return true;

        }

foreachに突っ込んで、無限に流れていく素数の列をみていると、確かに素数って極端な偏りなく分布してるんだ、ってことを実感できますｗ
一応、BigIntegerを使っているので、どんな大きな数になっても延々と列挙できます。ちゃんと確認はしてないけど。。。
f:id:minami_SC:20140228213400p:plain

てことで、原理的にはこのプログラムを放置しておけば、素数の世界記録に挑戦できるはずｗ
ただ、自分の環境でさっき動かし続けてみたけど、
1000000番目の素数を求めるのに230秒ほどかかりました。

            var sw = System.Diagnostics.Stopwatch.StartNew();
            var i = GetPrimeNumbers().ElementAt(100000-1);
            Console.WriteLine(i);
            Console.WriteLine("計算時間: {0}ms", sw.ElapsedMilliseconds);

f:id:minami_SC:20140228213008p:plain
これでもまだ8桁の素数です。
wikipediaで調べたところ、現時点で分かっている最大の素数は、十進法で表した時の桁数は1742万5170桁だそうです。