Eratosthenes篩選法求小于N的所有素數個數

2019-11-09 21:00:17

字體：大中小

來源：轉載

供稿：網友

求出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); }};

上一篇：BZOJ 1112: [POI2008]磚塊Klo 平衡樹，思維，枚舉

下一篇：石子合并（一）