科普篇:筛法是一种简单检定的算法。据说是古希腊的（Eratosthenes，约公元前274～194年）发明的，又称（sieve of Eratosthenes）.

说实话,之前我在求质数的场合都是验证某一数是否为质数的,用定义求即可方便的得出结论,代码如下:

01:  public static bool IsPrime(int n)02:  {
    //判断n是否是质数03:      if (n < 2) return false;04:      for (int i = n - 1; i > 1; i--)05:      {
    //n除以每个比n小比1大的自然数06:          if (n % i == 0)07:          {
    //如果有能被整除的，则不是质数08:              return false;09:          }10:      }//否则则为质数11:      return true;12:  }

但是用这种方法的话,如果要求两个数x和y之间的所有质数,就要用循环判断:

1:  for (int i = x; i < y; i++)2:  {3:      if (IsPrime(i))4:      {5:          Console.Write(i);6:      }7:  }

今天翻书偶然看到了筛法可能更加适合处理这样的问题--求某上限内的所有质数:

01:  private static List
     
       GenPrime(int j)02:  {03:      List
      
        ints=new List
       
        ();04:      BitArray bts=new BitArray(j+1);05:      for (int x = 2; x < bts.Length / 2; x++)06:      {07:          for (int y = x + 1; y < bts.Length; y++)08:          {09:              if (bts[y] == false && y % x == 0)10:              {11:                  bts[y] = true;12:              }13:          }14:      }15:      for (int x = 2; x < bts.Length; x++)16:      {17:          if (bts[x] == false)18:          {19:              ints.Add(x);20:          }21:      }22:      return ints;23:  }
       
      
     

不过如果要求范围内质数的话也需要求两个范围的差集:

1:  List
     
       ListResult = GenPrime(x).Except(GenPrime(y)).ToList();
     

之后又在另一篇高手的博客中发现了一篇线性的筛法算法,我将之改为了C#代码:

01:  private static List
     
       GenPrime1(int x)02:  {03:      int num_prime = 0;04:      List
      
        ints = new List
       
        ();05:      BitArray isNotPrime = new BitArray(x);06:      for (int i = 2; i < x; i++)07:      {08:          if (!isNotPrime[i])09:          {10:              ints.Add(i);11:              num_prime++;12:          }       13:          for (int j = 0; j < num_prime && i * ints[j] < x; j++)14:          {15:              isNotPrime[i * ints[j]] = true;16:              if (!Convert.ToBoolean(i % ints[j]))                  17:                  break;18:          }19:      }20:      return ints;21:  }
       
      
     

传送到原帖:

PS.第一次写博客,如有不足的地方请告诉我,我一定改!