エラトステネスの篩
問題
エラトステネスの篩を使って入力値以下の素数を求めましょう。
篩と書いて「ふるい」と読みます。難しいですね(2敗)
入力
・素数を求める範囲の最大値
・不適当な値が入力された場合、エラー落ちしてもいい
出力
・入力値以下の素数の数
・スペース区切りで、求めた素数のリスト
エラトステネスの篩
エラトステネスの篩 - Wikipedia
1) 求める範囲の最大値を20とします。
2) 2から始まる20までのリストを作ります
Prime list = {2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}
3) リストの1番目の数「2」の倍数を削除します(2は残す)
Prime list = {2,3,5,7,9,11,13,15,17,19}
4) 次にリストの2番目の数である「3」の倍数を削除します(3は残す)
Prime list = {2,3,5,7,11,13,17,19}
5) 3番目の「5」は、20の平方根(4.472…)より大きいので操作を終了します
6) リストに残った数が20以下の素数です
例
素数を求める範囲の最大値を入力してください >100 素数25個 素数リスト 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
解答例
using System; using System.Collections.Generic; namespace エラトステネスの篩 { class Program { static void Main(string[] args) { List<int> pl = new List<int>(); Console.WriteLine("素数を求める範囲の最大値を入力してください"); int n = int.Parse(Console.ReadLine()); for (int i = 2; i <= n; i++) { pl.Add(i); } for (int i = 0; pl[i] < Math.Sqrt(n); i++) { for (int j = pl.Count - 1; pl[j] != pl[i]; j--) { if (pl[j] % pl[i] == 0) pl.RemoveAt(j); } } Console.WriteLine("素数" + pl.Count + "個"); Console.WriteLine("素数リスト"); foreach (int p in pl) { Console.Write("{0} ", p); } } } }