Count Primes | Leetcode

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.

---

Solution: Use the Sieve of Eratosthenes algorithm to find prime numbers.

public class Solution {
    public int countPrimes(int n) {
        // Use <= 2 because we are taking only numbers
        // less than n, excluding n.
        if (n <= 2) return 0;
        
        // We use "notPrime" instead of "prime" so that we
        // don't need to initialize them to all true to begin.
        boolean[] notPrime = new boolean[n];
        int sqrt = (int) Math.sqrt(n - 1);
        
        for (int i = 2; i <= sqrt; i++) {
            if (notPrime[i]) continue;
            
            for (int j = i + i; j < n; j += i) {
                notPrime[j] = true;
            }
        }
        
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (!notPrime[i]) count++;
        }
        return count;
    }
}