# [leetcode] Count Primes

### Count Primes

Description:

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

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

A naive approach, check each i smaller than n that is prime or not.

O(n^2), time limit exceeded.

```class Solution {
public:
int countPrimes(int n) {
if(n <= 2) return 0;
int count = 0;
for(int i = 2; i < n; i++){
if(isPrime(i)){
count++;
}
}
return count;
}
bool isPrime(int n){
for(int i = 2; i <= n / 2; i++){
if(n % i == 0){
return false;
}
}
return true;
}
};```

n log log n complexity. But I don’t know how to prove it.

```class Solution {
public:
int countPrimes(int n) {
if(n <= 2) return 0;
bool map[n];
memset(map, true, sizeof(map));
map[0] = map[1] = false; // not a prime
for(int i = 2; i <= sqrt(n); i++){
if(map[i] == false) continue; // not a prime
for(int t = 2; t * i < n; t++){
map[t * i] = false; // not a prime
}
}
int count = 0;
for(int i = 2; i < n; i++){
if(map[i] == true) count++;
}
return count;
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.