你的位置:首页 > ASP.net教程

[ASP.net教程]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.第一次写博客,如有不足的地方请告诉我,我一定改!