```
public class Solution {
public int countPrimes(int n) {
if (n<3){
return 0;
}
boolean[] notPrimes = new boolean[n];
double sq = Math.sqrt(n);
for (int i=3;i<sq;i=i+2){//do odd
int jLimit = (n-1)/i;
for (int j=i;j<=jLimit;j=j+2){
notPrimes[i*j] = true;
}
}
int count = 0;
for (int i=2;i<n;i++){
if (notPrimes[i]){
count++;
}
}
return n/2-count; //divide n by 2 to subtract evens
}
}
```