# My accepted c++ code, 128ms

• Give a number N, it goes form 2 to n - 1, and remove all the multiples of N.

For example, when n is 8:

N=2: 2(×),3,4(×),5,6(×),7

N=3: 2(×),3(×),4(×),5,6(×),7

N=4: 2(×),3(×),4(×),5,6(×),7

N=5: 2(×),3(×),4(×),5(×),6(×),7

N=6: 2(×),3(×),4(×),5(×),6(×),7

N=7: 2(×),3(×),4(×),5(×),6(×),7(×)

``````class Solution {
public:
int countPrimes(int n) {
if (n < 2)
return 0;
std::vector<int> flag(n - 2, 1);
int res = 0;
for (int i = 0; i < n - 2; ++i)
if (flag[i]) {
++res;
for (int j = i; j < n - 2; j += i + 2)
flag[j] = 0;
}
return res;
}
};
``````

Update:

``````class Solution {
public:
int countPrimes(int n) {
if (n <= 2)
return 0;
std::vector<int> flag(n, 1);
int res = 1, sqr = std::sqrt(static_cast<double>(n)), i = 3;
for (; i <= sqr; i += 2)
if (flag[i]) {
++res;
for (int j = i * i; j < n; j += i)
flag[j] = 0;
}
for (; i < n; i += 2)
res += flag[i];
return res;
}
};``````

• "std::vector<int> flag(n - 2, 1);"meas?

• it means flag has (n-2) int variables, and every variable is set value 1.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.