# O(n) solution with time complexity analysis - JAVA

• 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).

• you have an inner for loop and a outer for loop. Time complexity is not O(n)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.