204. Count Primes

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

Example:

Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Solution

筛选法

Complexity

Code

    public int countPrimes(int n) {
        if(n < 2) return 0;
        int[] notPrimes = new int[n];
        for(int i = 2; i*i < n; i++){
            if(notPrimes[i] == 0){
                for(int j = i * i; j < n; j+=i){
                    notPrimes[j] = 1;
                }
            }
        }
        int res = 0;
        for(int i = 2; i < n; i++)
            if(notPrimes[i] == 0){
                res++;
            }
        return res;
    }