Eratosthenes篩選法求小于N的所有素數(shù)個數(shù)

2019-11-10 18:45:25

字體：大中小

供稿：網(wǎng)友

求出1~N范圍中所有的素數(shù)，在leetcode中做過這個題目，我想從對每個1~N進行一次遍歷，每個數(shù)判斷一次是否是素數(shù)。

判斷一個數(shù)是否是素數(shù)的復雜度本身也是挺高的，再進行一次迭代，在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全是素數(shù)，然后從第一個素數(shù)2的平方4開始，去掉因子包括2的數(shù)，例如4、6、8…. 然后從后一個素數(shù)3的平方9開始剔除，因子包括3的數(shù)，例如9、12等。。。

最后剩下的數(shù)就是所有的素數(shù)。

代碼

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;//第一個素數(shù) int j = p*p; int c = 0; while (j <= n) { while (j <= n) { primes[j] = false; j += p; } ++p; while (!primes[p])//尋找下一個素數(shù) { ++p; } j = p*p;//從p的平方開始篩選 } return std::count(primes.begin(), primes.end()-1,true); }};

上一篇：最大乘積

下一篇：poj1517