一週間で身につくC# の勉強中14

prob8-12

エラトステネスのふるいを用いて、100以下の素数を全て求めるプログラムを作ってください。（配列を用いること）“エラトステネスのふるい”とは、数値の一覧表を作り、表の中から、最初の素数である2の倍数（ただし、2を除く）を全て消去し、その次に、残った数値の中から最小の数（この場合は3）の倍数を表から全て削除していく、ということを繰り返していく方法です。表の中の一番大きな数での処理が終わった段階で残った数値が、素数になります。

この場合、１は最初から除外します。

ステップ１：１はさいしょから除外。まずは、１より大きい最初の素数である、２を残す。 2  3  4  4  5  6  …  100

ステップ２：２の倍数を全て消去 3  5  7  9  5  6  …  99

ステップ３：残った数のうち最小の数である３を残し、３の倍数を全て消去 5  7  11  13  17  6  …  97

・・・同様の処理を、100以下の全ての数に繰り返す。

考え方のポイント

非常に難しかったです。無限ループをつかい繰り返し素数で割り算しています。また無限ループのブレークポイントを定めるためにもforeachを使っています。途中何度もConsole.Writeで配列を出して確かめながらプログラムを作りました。どうにか出来上がったという感じなので無駄が多いプログラムになっているかもしれません。

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

namespace prob8_12__2
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] hi = new int[99];

            for (int i = 0; i < 99; i++)
            {
                hi[i] = i + 2;　//最初の数字は２だから
            }
            int hajime = 2;
            while (true)
            {
                for (int i = 0; i < 99; i++)
                {
                    //最初の素数を残すし、割り切れる数字を0に入れ替える
                    if (hi[i] % hajime == 0 && hi[i] > hajime) 
                    {
                        hi[i] = 0;
                    }
                }
                int j = 0;
                //次の素数を探す（最初の素数の次に大きい数）
                while (hi[j] < 98)
                {
                    j++;
                    if (hi[j] > hajime)　//hajimeより大きい数を見つけたらbreak
                    {
                        break;
                    }
                }
                hajime = hi[j];
                //無限ループのbreakポイントを見つける、配列の一番大きい数とhajimeが同じなら
                int dai = 0;
                foreach (int k in hi)
                {
                    if (k > dai)
                    {
                        dai = k;
                    }
                }
                if (hajime == dai)
                {
                    break;
                }

            }
            //無限ループをbreakしたために一番最後の数字(hajime）で配列を処理できていないのでここで行う
            for (int i = 0; i < 99; i++)
            {
                if (hi[i] % hajime == 0 && hi[i] > hajime)
                {
                    hi[i] = 0;
                }
            }
            //余分な0の入っていない配列を作る。まずは配列の長さを調べる
            int cnt = 0;
            int num = 0;
            foreach (int i in hi)
            {
                if (i != 0)
                {
                    cnt++;
                }
            }

            int[] hi1 = new int[cnt];
            foreach (int i in hi)
            {
                if (i != 0)
                {
                    hi1[num] = i;
                    num++;
                }
            }


            foreach (int i in hi1)
            {
                Console.Write("{0} ", i);
            }
        }
    }