leetcode204. 计数质数

埃氏筛

如果 xx 是质数，那么大于 x 的倍数 2x,3x,… 一定不是质数

class Solution {
public:
    int countPrimes(int n) {
        int ans=0;
        vector<bool> prime(n,true);
        for(int i=2;i<n;i++){
            if(prime[i]){
                ans++;
                if((long long)i*i<n){
                    for(int j=i*i;j<n;j+=i){
                        prime[j]=false;
                    }
                }
            }
        }
        return ans;
    }
};

线性筛

class Solution {
public:
    int countPrimes(int n) {
        vector<bool> isprime(n,true);
        vector<int>primes;
        for(int i=2;i<n;i++){
            if(isprime[i]){
                primes.push_back(i);
            }
            for(int j=0;j<primes.size()&&i*primes[j]<n;j++){
                isprime[i*primes[j]]=false;
                if(i%primes[j]==0)break;
            }
        }           
        return primes.size();
    }
};