```
int countPrimes(int n) {
if (n <= 2) return 0;
bool* primes = new bool[n];
int sqr = sqrt(n-1);
for (int i = 3; i <= sqr; i += 2){
if (primes[i] == false){
for (int j = i * i; j < n; j += i)
primes[j] = true;
}
}
int sum = 1;
for (int i = 3; i < n; i += 2)
sum += (primes[i] == false) ? 1 : 0;
return sum;
}
```