素数を求める
数学ガールの秘密ノート「整数で遊ぼう」を読んでたところ、
エラトステネスのふるいで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;
}