204. Count Primes

Leetcode Hash Table Math

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.

分析

The Sieve of Eratosthenes is one of the most efficient ways to find all prime numbers up to $n$.

We start off with a table of $n$ numbers. Let's look at the first number, 2. We know all multiples of 2 must not be primes, so we mark them off as non-primes. Then we look at the next number, 3. Similarly, all multiples of 3 such as 3 × 2 = 6, 3 × 3 = 9, ... must not be primes, so we mark them off as well. Now we look at the next number, 4, which was already marked off. So we can skip 4 immediately and go to the next number, 5. Now, all multiples of 5 such as 5 × 2 = 10, 5 × 3 = 15, 5 × 4 = 20, 5 × 5 = 25, ... can be marked off.

In fact, we can mark off multiples of 5 starting at 5 × 5 = 25, because 5 × 2 = 10 was already marked off by multiple of 2, similarly 5 × 3 = 15 was already marked off by multiple of 3. Therefore, if the current number is p, we can always mark off multiples of p starting at $p^2$, then in increments of p: $p^2 + p, p^2 + 2p$, ...

The terminating loop condition can be $p < \sqrt{n}$, as all non-primes $\ge \sqrt{n}$$ must have already been marked off.

The Sieve of Eratosthenes uses an extra $O(n)$ memory and its runtime complexity is $O(n \log \log n)$.

public int countPrimes(int n) {
    // boolean[] are initialed as false by default
    boolean[] notPrime = new boolean[n];
    for (int i = 2; i*i < n; i++) {
        if (!notPrime[i]) {
            for (int j = i*i; j < n; j += i)
                notPrime[j] = true;
        }
    }
    int count = 0;
    for (int i = 2; i < n; i++)
        if (!notPrime[i]) count++;

    return count;
}

但其实Sieve of Eratosthenes方法并不快，虽然它的算法复杂度非常好。因为它反复需要计算乘积，对于整数来说，它的表示范围本来就很小，这种算法上的优化并没有什么用。反而下面的快一些，把判断条件改为$i<n$。

public int countPrimes(int n) {
    boolean[] notPrime = new boolean[n];
    int count = 0;
    for (int i = 2; i < n; i++) {
        if (notPrime[i] == false) {
            count++;
            for (int j = 2*i; j < n; j += i)
                notPrime[j] = true;
        }
    }

    return count;
}