Eratosthenes筛选法

说到素数，最基本的算是一百以内的那些数了。这些数在数学竟赛中常常会被用到。比如说有这样一道题：“一百以内有多少在加2后仍然是素数的素数？”11和17就是这样的素数。如果对素数很熟悉的话，就能迅速得出答案。

那么，给定一个一百以内的数，如何迅速判断它是不是素数呢？

一个最简单的方发就是“埃拉托斯特尼筛法” (Sieve of Eratosthenes)。如上图所示，给出要筛数值的范围n，找出n√以内的素数p1,p2,…,pk。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个素数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个素数5筛，把5留下，把5的倍数剔除掉；不断重复下去......。

using System;
using System.Collections.Generic;
using System.Text;

namespace 产生素数
{
    class PrimeGenerator
    {
        private static bool[] crossedOut;
        private static int[] result;
        public static int[] GeneratePrimeNumbers(int maxValue)
        {
            if (maxValue < 2)
            {
                return new int[0];
            }
            else
            {
                UncrossIntegersUpTo(maxValue);
                CrossOutMultiples();
                PutUncrossedIntegersIntoResult();
                return result;
            }
        }

        private static void PutUncrossedIntegersIntoResult()
        {
            result = new int[NumberOfUncrossedIntegers()];
            for (int j = 0, i = 2; i < crossedOut.Length; i++)
            {
                if (NotCrossed(i))
                {
                    result[j++] = i;
                }
            }
        }

        private static bool NotCrossed(int i)
        {
            return crossedOut[i] == false;
        }

        private static int NumberOfUncrossedIntegers()
        {
            int count = 0;
            for(int i=2;i<crossedOut.Length;i++)
            {
                if (NotCrossed(i))
                {
                    count++;
                }
            }
            return count;
        }

        private static void CrossOutMultiples()
        {
            int limit = DetermineIterationLimit();
            for (int i = 2; i <= limit; i++)
            {
                if (NotCrossed(i))
                {
                    CrossOutMultiplesOf(i);
                }
            }
        }

        private static void CrossOutMultiplesOf(int i)
        {
            for(int multiple=2*i;multiple<crossedOut.Length;multiple+=i)
            {
                Console.WriteLine("multiple{0}  {1}", multiple,i);
                crossedOut[multiple] = true;
            }
        }

        private static int DetermineIterationLimit()
        {
            double interationLimit = Math.Sqrt(crossedOut.Length);
              return (int)interationLimit;
        }

        private static void UncrossIntegersUpTo(int maxValue)
        {
            crossedOut = new bool[maxValue + 1];    
            for (int i = 2; i < crossedOut.Length; i++)
            {
                crossedOut[i] = false;
            }
        }
    }
}