```
public class Solution {
public int countPrimes(int n) {
if(n < 3)
return 0;
int[] pArray = new int[n+1];
int primeCount =0;
for(int i =2; i < pArray.length-1; i++)
{
if(pArray[i]==-1)
continue;
primeCount++;
int num = i;
while(num < pArray.length-1)
{
pArray[num] = -1;
num += i;
}
}
return primeCount;
}
}
```

It goes twice over the array O(2n) which can be taken same as O(n). Once to check all number if they are prime or not, second if a number is prime (not marked as -1) then make all its multiple as -1.