204. Count prime

Method 1 Linear sieve

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

Accepted
66/66 cases passed (544 ms)
Your runtime beats 17.94 % of cpp submissions
Your memory usage beats 52.16 % of cpp submissions (36.3 MB)

Method 2 Ethmoid

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

Accepted
66/66 cases passed (156 ms)
Your runtime beats 91.09 % of cpp submissions
Your memory usage beats 93.42 % of cpp submissions (10 MB)