```
public class Solution {
public int countPrimes(int n) {
if(n < 3) {
return 0;
}
boolean[] status = new boolean[n - 2]; //hold status for number [2 ... n -1]
for(int i = 2; i <= Math.sqrt(n - 1); i++) {
if(status[i - 2]) { //number i has been traversed, skip it
continue;
}
for(int j = i; j <= (n - 1) / i; j++) {
status[i * j - 2] = true;
}
}
int result = 0;
for(boolean stat : status) {
if(!stat) {
result++;
}
}
return result;
}
}
```

Time complexity will be O(N), space complexity is also O(N), which can be reduced by using bit array but still linear.

** Analysis**:

For each number k, which let's say, can be factored as p1 * p2 * ... * pm, it will be traversed m times. Given that k locates within Java Integer range (k <= 2^63 - 1), m will be smaller than 63 since any pi >= 2. Thus, we can find a constant c (c = 63 here), having the running time T <= c * n, which means the time complexity is O(N).