LINQでエラトステネスの篩の素朴な実装

エラトステネスの篩の実装メモ

という記事があって、エラトステネスの篩はLINQが遅延評価だということを実感することができる良い教材だなぁ
と思ったのでLINQを使って素朴な実装をしてみます。

みんな知ってると思うけど知らない人はこちら
エラトステネスの篩

コード

エラトステネスの篩

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Hurui
{
    class Program
    {

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

        /// <summary>
        /// エラトステネスの篩のとても素直な実装
        /// </summary>
        /// <returns></returns>
        static IEnumerable<int> Primes()
        {
            //素数候補リスト
            var ps = Ns(); //自然数列があります

            while (true)
            {
                var prime = ps.First(); //リストの一番最初は素数です
                ps = ps.Where(i => i % prime != 0); //一番最初で割り切れるものを落としたものが新たな素数候補です
                yield return prime; //リストの一番最初返します
            }

        }

        /// <summary>
        /// 二以上の自然数の無限列(実際はInt32.MaxValueまでだけど)
        /// </summary>
        /// <returns></returns>
        static IEnumerable<int> Ns()
        {
            int i = 2;
            while (true) yield return i++;
        }
    }
}

解説

Ns()について

Nsは二以上の自然数の無限列(実際はInt32.MaxValueまで)を返すメソッドです。
このメソッドはもちろん読めば分かる通り無限ループになっています。
が、Ns()を呼び出しただけではプログラムは問題なく終了します。

終了するコードの例

Ns();
Console.WriteLine("終了"); //一瞬でここに到達します。

終了するコードの例

Ns().ToArray();//ここですべての要素を計算して配列化しようとするのでOutOfMemoryになります
Console.WriteLine("終了"); //ここに到達できません

これはNs()は列挙の仕方を定義しているだけで実際にはまだ列挙していないからです。
だからNs()の中身をすべて出力するようなプログラムは終了しませんが一方で呼び出しただけだと計算をしていないためすぐにこのメソッドは終了することになります。

またNs().Take(2)のように先頭の方で処理を打ち切るようなメソッドを挟めば値を取り出すことができます。
Ns().Take(2).ToArray()とすれば先頭の方のみの配列を作ることができます。

この用に必要になるまで値を評価しないことを遅延評価と言います。

ちなみにBigIntegerじゃないのは十分素数のメソッドが遅かったからです。

Primesについて

これは無限列が作れるのでエラトステネスの篩の本質部分をそのままメソッド化しただけです。
psは素数候補のリストになります。（つまりまだ今までの素数で割り切れていない数字の列）
ループの中身は

素数候補の先頭は素数確定なので素数primeをとっておきます
素数候補からprimeで割り切れた素数候補でなくなったものを省きます
- ここでも、やはりWhereは遅延評価なのですぐに終わります。
primeをリストの要素として返却します

というふうになっています。
もちろんこのメソッドも無限列なので終了しません。
が、今回は別に終了しなくて良いのでそのまま出力しています。Ctrl+Cで止まります。

ちなみにですが、このpsは素数の数pnが増えていくに従ってWhereメソッドがpn個連続しているような状態になります。ですので、Firstで先頭要素を取得するタイミングで時間がかかることになります。もちろん空間計算量もO(1)に見えたりしますがそんなことはなくO(n)です。

今回はLINQは遅延評価だよというのを確かめたかったのでこんな感じにしましたがもし使うことがあればこのコードを使うことは絶対におすすめしません。
無駄いっぱいあるのですよ

Nsはintにしたんだから結局はRangeメソッドで良かった気がした