Prime Number

• https://leetcode.com/problems/count-primes/

Enumerate all primes to N

Count Prime

Time Complexity: The time to sift out the multiples of p is proportional to n/p, so the overall time complexity is O(n/2 + n/3 + n/5 + n/7 + n/11 + ....)

Yield to O(nloglogn)

public int countPrimes(int n) {
    if (n == 0 || n == 1 || n == 2) return 0;

    boolean[] primeArray = new boolean[n];

    for (int i = 2; i < n; i++) {
        primeArray[i] = true;
    }

    for (int i = 2; i < n; i++) {
        if (primeArray[i]) {
            for (int j = i + i; j < n; j = j + i) {
                primeArray[j] = false;
            }
        }
    }

    int count = 0;
    for (int i = 2; i < n; i++) {
        if (primeArray[i])
            count++;
    }
    return count;
}