Count primes

Description:

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

The hint of the problem gives us lots of explanations. Basically, we only need to count till sqrt(n) because all the numbers greater than sqrt(n) is a mirror of the previous one. For example, 2 * 6  and 6 * 2 are mirror to each other so we only need to consider 2 * 6. Now for each prime we have seen, the multiples of the number can be wiped out since it can be divided by the prime we see. And this is called Sleve of Eratosthenes.

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