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