204. 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.

Solution

public class Solution {
     public int countPrimes(int n) {
        if (n == 0) return 0;
        if (n == 1) return 0;
        if (n == 2) return 0;

        n = n-1;

        boolean[] isPrime = new boolean[n+1];
        for(int i = 2; i <= n; i ++) {
            isPrime[i] = true;
        }

        for(int i = 2; i <= Math.sqrt(n); i ++) {
            if (isPrime[i]) {
                for(int j = 2 *i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }


        int result = 0;
        for(int i = 2; i <= n; i ++) {
            if (isPrime[i]) {
                result ++;
            }
        }

        return result;
    }
}