204. 计数质数

204. 计数质数

最简单的质数筛
埃式筛法

class Solution {
public:
    int countPrimes(int n) {
        if(!n) return 0;
        bool notprime[n];
        memset(notprime,0,sizeof notprime);
        
        for(int i=2;i<n;i++){
            for(int j=2;i*j<n;j++){
                notprime[i*j]=true;
            }
        }
        
        int cnt=0;
        for(int i=2;i<n;i++)
            if(!notprime[i])
                cnt++;
        return cnt;
    }
};