C#篩法求出范圍內的所有質數，

C#篩法求出范圍內的所有質數，

   
    科普篇:篩法是一種簡單檢定素數的算法。據說是古希臘的埃拉托斯特尼（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<int> GenPrime(int j)
02:  {
03:      List<int> ints=new List<int>();
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<int> ListResult = GenPrime(x).Except(GenPrime(y)).ToList();

  
之後又在另一篇高手的博客中發現了一篇線性的篩法算法,我將之改為了C#代碼:

  
01:  private static List<int> GenPrime1(int x)
02:  {
03:      int num_prime = 0;
04:      List<int> ints = new List<int>();
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.第一次寫博客,如有不足的地方請告訴我,我一定改!