プログラム問題集

プログラム問題集

多分プログラミングの問題集でも書いていく

エラトステネスの篩

問題

 エラトステネスの篩を使って入力値以下の素数を求めましょう。
篩と書いて「ふるい」と読みます。難しいですね(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
解答例

C#

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);
            }
        }
    }
}