### Description

Count the number of prime numbers less than a non-negative number, n.

Example:

Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

### Analysis

It is easy to come up with the brute force method. When judging a prime number, we need to judge if there is a divisor of n from $$2$$ to $$\sqrt{n}$$. So the time complexity is $$O(n\sqrt{n})$$.

However, we have a efficient method, Sieve of Eratosthenes. We define a boolean vector that reflects whether the number is prime. Set the initial values be true. For the number from $$2$$ to $$n-1$$, if one number is true, then set the multiples of it be false. In the meantime, count the number that is true.

### Solution

class Solution {
public int countPrimes(int n) {
if(n<=2) return 0;
int res=0;
boolean[] pri=new boolean[n-2];
for(int i=2;i<n;i++)
{
pri[i-2]=true;
}
for(int i=2;i<n;i++)
{
if(pri[i-2]==true)
{
res++;
for(int j=2;i*j<n;j++)
pri[i*j-2]=false;
}
}
return res;
}
}


### Reference

[1] https://github.com/EdwardShi92/Leetcode-Solution-Code/blob/master/CountPrimes.java