```
public class Solution {
public int countPrimes(int n) {
if(n<=2)return 0;
int count=n/2; //only odd numbers make sense (note 2 as 1)
boolean[] prime = new boolean[n];
Arrays.fill(prime,true);
for(int i=3;i<Math.sqrt(n);i+=2){
if(!prime[i]) continue;
int num = 3*i;
while(num<n){
if(prime[num]) count--;
prime[num] = false;
num+=2*i;
}
}
return count;
}
}
```