```
public int countPrimes(int n) {
if (n < 3) return 0;
int primeNum = n / 2; // Count all the odd number
boolean[] isPrime = new boolean[n];
int sqrtN = (int) Math.sqrt(n);
for (int i = 3; i <= sqrtN; i += 2) {
if (!isPrime[i]) {
for (int j = i * i; j < n; j += i * 2) {
primeNum -= (isPrime[j])? 0: 1;
isPrime[j] = true;
}
}
}
return primeNum;
}
```