204. Count Primes

Description:

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

Solution:

If x is prime, x * 2, x * 3, ... are not primes.

We go through the numbers from 2 to n (apparently 1 is not prime).

If we find this number is prime, we add the count and set all its multiples to “not prime”.

If we find this number is not prime, we simply start to check the next number.

This algorithm is called "Sieve of Eratosthenes".

The time complexity is O(nloglogn).



Code:

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