[C#]エラトステネスのふるいで素数を求める

素数を求める

数学ガールの秘密ノート「整数で遊ぼう」を読んでたところ、
エラトステネスのふるいで200以下の素数を全て求める問題がありました。

※エラトステネスのふるいはWikipediaを参照

プログラムで書いてみよう！

手書きで表を書いて、消し込みをして、素数を求めたのではありますが、
じゃ、同じ手順となるようにプログラムを書いてみよう！と思いました。

書いてみた(修正後)

※albireoさんに頂いた指摘と、「抽出したメソッド、素数求めるのと、ディクショナリの更新をどっちもしてるのってどうなの？」との指摘から修正しました。

Form1.cs

private void button1_Click(object sender, EventArgs e)
{
    //エラトステネスのふるい
    //範囲の指定
    var from = 1;
    var to = 200;
    var range = Enumerable.Range(from, to);

    //範囲内全数のリストを作る。
    //1番目は数字、2番目は0：判定前、1:消した(素数でない)、2:○をつけた(素数)
    Dictionary<int, int> dic = new Dictionary<int, int>();
    range.ToList().ForEach(i => dic.Add(i, 0));

    //1を消す→単数
    dic[1] = 1;

    while (true)
    {
        //素数判定＋消し込み
        int primeNumber = dic.Where(kvp => kvp.Value == 0).Min(kvp => kvp.Key);

        //素数と設定
        dic[primeNumber] = 2;

        //残っている数字のうち素数の倍数のみ抽出
        var targets = dic.Where(kvp => kvp.Value == 0 && kvp.Key % primeNumber == 0).Select(kvp => kvp.Key).ToList();

        //素数の倍数を消し込む
        targets.ForEach(num => dic[num] = 1);

        //素数の2乗が範囲の最後より大きい場合、そこで終了
        if (primeNumber * primeNumber > to) { break; }
    }
    //残っている数字を抽出。
    var remainNumbers = dic.Where(kvp => kvp.Value == 0).Select(v => v.Key).ToList();
    //残っている数字は全部素数！
    remainNumbers.ForEach(v => dic[v] = 2);

    //素数のみ出力
    var primeNumbers = dic.Where(kvp => kvp.Value == 2).Select(kvp => kvp.Key).OrderBy(v => v).ToList();
    Console.WriteLine(string.Join(",", primeNumbers));
}

##出力結果
以下の通り。手書きで求めたものと合ってる。OK！

2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199

書いてみた(修正前)

Form1.cs

private void button1_Click(object sender, EventArgs e)
{
    //エラトステネスのふるい
    //範囲の指定
    var from = 1;
    var to = 200;
    var range = Enumerable.Range(from, to);

    //範囲内全数のリストを作る。
    //1番目は数字、2番目は0：判定前、1:消した(素数でない)、2:○をつけた(素数)
    Dictionary<int, int> dic = new Dictionary<int, int>();
    range.ToList().ForEach(i => dic.Add(i, 0));

    //1を消す→単数
    dic[1] = 1;

    while (true)
    {
        //素数判定＋消し込み
        int primeNumber = SelectPrimeNumber(dic);

        //素数の2乗が範囲の最後より大きい場合、そこで終了
        if (primeNumber * primeNumber > to) { break; }
    }

    //残っている数字を抽出。
    var remainNumbers = dic.Where(v => v.Value == 0).Select(v => v.Key).ToList();
    //残っている数字は全部素数！
    remainNumbers.ForEach(v => dic[v] = 2);

    //素数のみ出力
    var primeNumbers = dic.Where(v => v.Value == 2).Select(v => v.Key).OrderBy(v => v).ToList();
    Console.WriteLine(string.Join(",", primeNumbers));
}


private int SelectPrimeNumber(Dictionary<int, int> dic)
{
    //消えてないうちの最小の値を求める
    var primeNumber = dic.Where(v => v.Value == 0).Min(v => v.Key);

    //素数と設定
    dic[primeNumber] = 2;

    //残っている数字のみ抽出
    var targets = dic.Where(v => v.Value == 0).Select(v => v.Key).ToList();

    //素数の倍数を消し込む
    targets.ForEach(key => { if (key % primeNumber == 0) { dic[key] = 1; } });
    
    //素数を返す
    return primeNumber;
}