///<summary> /// 判断自然数是否是质数 ///</summary> ///<param name="n">需要判断的数</param> ///<returns>是/否</returns> publicstaticboolIsPrime(int n) { if (n < 2) returnfalse; for (var i = n - 1; i > 1; i--) { //n除以每个比n小比1大的自然数 if (n % i == 0) //如果有能被整除的,则不是质数 returnfalse; } //否则则为质数 returntrue; }
获取范围内质数
1 2 3 4 5 6 7 8 9 10 11 12
///<summary> /// 获取自然数区间内的所有质数 ///</summary> ///<param name="startInt">自然数区间起始点</param> ///<param name="endInt">自然数区间终点</param> ///<returns>自然数区间内的所有质数的集合</returns> publicstatic IEnumerable<int> GetPrimes(int startInt, int endInt) { for (var i = startInt; i <= endInt; i++) if (IsPrime(i)) yieldreturn i; }
筛法
什么是筛法
科普篇:筛法是一种简单检定质数的算法。据说是古希腊的埃拉托斯特尼(Eratosthenes)发明的,又称埃拉托斯特尼筛法(sieve of Eratosthenes).
使用筛法求某上限内所有质数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
///<summary> /// 求某上限内的所有质数 ///</summary> ///<param name="j">上限自然数</param> ///<returns>上限内所有质数</returns> publicstatic IEnumerable<int> GenPrime(int j) { var bts = new BitArray(j + 1); for (var x = 2; x < bts.Length / 2; x++) for (var y = x + 1; y < bts.Length; y++) if (bts[y] == false && y % x == 0) bts[y] = true; for (var x = 2; x < bts.Length; x++) if (bts[x] == false) yieldreturn x; }