Count Primes

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

• Time: O(n)
• Space: O(1)

public int countPrimes(int n) {
    boolean[] index = new boolean[n];
    for (int i = 2; i < n; i++) {
        index[i] = true;
    }
    for (int i = 2; i * i < n; i++) {
        if (!index[i])
            continue;
        for (int j = i * i; j < n; j += i) {
            index[j] = false;
        }
    }
    int count = 0;
    for (int i = 2; i < n; i++) {
        if (index[i]) {
            count++;
        }
    }
    return count;
}