```
public class Solution {
public int countPrimes(int n) {
if (n <= 2) return 0;
BitSet bs = new BitSet(n);
bs.set(0);
bs.set(1);
// skip 2, and all even numbers afterwards
int ind = 3, count = 1, sqrt = (int) Math.sqrt(Integer.MAX_VALUE);
while (ind < n) {
ind = bs.nextClearBit(ind);
// skip even numbers
while ((ind & 1) == 0) {
ind = bs.nextClearBit(++ind);
}
if (ind >= n) {
break;
}
count++;
// avoid overflow problem
if (ind >= sqrt) {
ind += 2;
continue;
}
// ind must be odd, so we make step an even number, so that every time, i is an odd number
for (int i = ind * ind, step = ind * 2; i < n; i += step) {
bs.set(i);
}
ind += 2;
}
return count;
}
}
```