1. Count Primes

~~1 is not prime! ~~

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

<N的所有质数！

Sieve of Eratosthenes:

.

public class Solution {
    public int countPrimes(int n) {

        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, 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;

    }
}