leetcode 204. Count Primes(线性筛素数)

Description:

Count the number of prime numbers less than a non-negative number, n.

题解：就是线性筛素数的模板题。

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