今更聞けないエラトステネスのふるい

エラトステネスのふるいを活用し、素数の判定を行います。

愚直な素数判定

まず初めに、エラトステネスのふるいを活用しないで素数の判定を行う方法から示します。

素数であるかを判定するには、検証したい数が、検証したい数以下の整数で割り切れるかを2まで繰り返せば良いです。
割り切れるかどうかを確認するため、検証したい数/2以上の数は確認する必要がありません。
また、数学的にはさらに√検証したい数まで確認すれば良い事が分かっています。

notEratosthenes.cs

        public void notEratosthenes(int num)
        {
            var answerList = new List<int>();

            for (int x = 2; x < num; x++)
            {
                var limit = (int)Math.Sqrt(x);
                int targetNum;

                for (targetNum = limit; targetNum > 1; targetNum--)
                {
                    if (x % targetNum == 0)
                    {
                        break;
                    }
                }

                if (targetNum == 1)
                {
                    answerList.Add(x);
                }
            }
            Console.WriteLine("answer");
            Console.WriteLine(string.Join(" ", answerList));
        }

エラトステネスのふるいを使った素数判定

愚直な解き方に対し、エラトステネスのふるいと呼ばれる方法は2〜√検証したい数までの倍数をふるい落としていくという方法です。

eratosthenes.cs

        public void eratosthenes(int num)
        {
            var answerArray = new int[num + 1];

            var limit = (int)Math.Sqrt(num);

            for(int i = 2;i <= limit;i++)
            {
                if(answerArray[i] == 0)
                {
                    for(int j = 2 * i;j <= num;j++)
                    {
                        if(j % i == 0)
                        {
                            answerArray[j] = 1;
                        }
                    }
                }
            }

            Console.WriteLine("answer");
            for(int i = 2; i <= num;i++)
            {
                if(answerArray[i] == 0)
                {
                    Console.Write(i + " ");
                }
            }
        }

計算量がO(nloglogn)となりました!!
競技プログラミング的な要素も入ってくるので、非常に勉強になりますね。