Eratosthenes筛选法求小于N的所有素数个数

2019-11-10 18:45:25

字体：大中小

来源：转载

供稿：网友

求出1~N范围中所有的素数，在leetcode中做过这个题目，我想从对每个1~N进行一次遍历，每个数判断一次是否是素数。

判断一个数是否是素数的复杂度本身也是挺高的，再进行一次迭代，在leetcode中的结果是超时：

class Solution {PRivate: bool isPrime(int n) { int sqrt_=sqrt(n); int i; for (i=2;i<=sqrt_;++i) { if(n%i==0) break; } if(i>sqrt_) return true; else return false; }public: int countPrimes(int n) { int count=0; for(int i=2;i<n;++i) { if(isPrime(i)) ++count; } return count; }};

Eratosthenes筛选法

既然筛选，先假定1~N全是素数，然后从第一个素数2的平方4开始，去掉因子包括2的数，例如4、6、8…. 然后从后一个素数3的平方9开始剔除，因子包括3的数，例如9、12等。。。

最后剩下的数就是所有的素数。

代码

class Solution {public: int countPrimes(int n) { if(n<2) return 0; vector<bool>primes(n + 1,true); primes[0] = false; primes[1] = false; int p = 2;//第一个素数 int j = p*p; int c = 0; while (j <= n) { while (j <= n) { primes[j] = false; j += p; } ++p; while (!primes[p])//寻找下一个素数 { ++p; } j = p*p;//从p的平方开始筛选 } return std::count(primes.begin(), primes.end()-1,true); }};

上一篇：最大乘积

下一篇：poj1517