Description:
Count the number of prime numbers less than a non-negative number, n.
Link:
https://leetcode.com/problems/count-primes/#/description
解题方法：
Time Complexity：
O(N*logN)
完整代码：
int countPrimes(int n)
{
if(n < 3)
return 0;
vector<bool> prime(n, true);
int cnt = 0;
for(int i = 2; i < n; i++)
{
if(!prime[i])
continue;
int ftr = 2;
while(i * ftr < n)
prime[i * ftr++] = false;
cnt++;
}
return cnt;
}
