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;
    }
};