Count Primes

Description:

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

Tips:

动归，想清楚prime的判断规则，注意i和j都从2开始循环即可， 还有就是2在这里不算质数。

优化的话可以先判断，如果notPrime[i] == false，可以直接continue。还有再优化的版本，见下。

复杂度：O(nlogn)

Code:

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

Optimized:

publib int countPrimes(int n) {
    if (n < 3)
        return 0;

    boolean[] f = new boolean[n];
    //Arrays.fill(f, true); boolean[] are initialed as false by default
    int count = n / 2;
    for (int i = 3; i * i < n; i += 2) {
        if (f[i])
            continue;

        for (int j = i * i; j < n; j += 2 * i) {
            if (!f[j]) {
                --count;
                f[j] = true;
            }
        }
    }
    return count;
}