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

港控/mmm° 2022-07-12 03:22 180阅读 0赞

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