Description

Submission

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

        int count = 0;
        for(int i = 0; i < n; ++i) {
            if(bucket[i]) count++;
        }
        return count;
    }
};