Count Primes

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

Solution1: 超时了

public class Solution {
    public int countPrimes(int n) {
        int count = 0;
        
        for (int i = 2; i <= n; i++) {
            if (isPrime(i)) {
                count++;
            }
        }
        return count;
    }
    
    public boolean isPrime(int x) {
        for (int i = 2; i <= Math.sqrt(x); i++) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }
}

Solution2: Sieve of Eratosthenes

Run time complexity is O(n log log n), space complexity is O(n)

public class Solution {
    public int countPrimes(int n) {
        int result = 0;
        
        boolean[] notPrime = new boolean[n];
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (!notPrime[i]) {
                int j = i * i;
                while (j < n) {
                    notPrime[j] = true;
                    j += i;
                } 
            }
        }
        
        for (int i = 2; i < n; i++) {
            if (!notPrime[i]) {
                result++;
            }
        }
        
        return result;
    }
}

Or: 更加清晰一点

public class Solution {
    public int countPrimes(int n) {
        int result = 0;
        
        boolean[] isPrime = new boolean[n];
        for(int i = 0; i < n; i++) {
            isPrime[i] = true;
        }
        
        // Loop's ending condition is i * i < n instead of i < sqrt(n)
        // to avoid repeatedly calling an expensive function sqrt().
        for (int i = 2; i * i < n; i++) {
            if (isPrime[i]) {
                int j = i * i;
                while (j < n) {
                    isPrime[j] = false;
                    j += i;
                } 
            }
        }
        
        for (int i = 2; i < n; i++) {
            if (isPrime[i]) {
                result++;
            }
        }
        
        return result;
    }
}