Count Primes

Question

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

Solution

这道题首先想到的方法是从1到n-1依次验证是否为prime。但是这样的时间复杂度为O(n^2)。

如果使用埃拉托斯特尼筛法（Sieve of Eratosthenes），则可以将时间复杂度降低到O(nloglogn)。具体方法如下：

这个算法的过程如上图所示，我们从2开始遍历到根号n，先找到第一个质数2，然后将其所有的倍数全部标记出来，然后到下一个质数3，标记其所有倍数，一次类推，直到根号n，此时数组中未被标记的数字就是质数。之所以不用考虑比自己小的倍数（比如3从3倍开始而不用考虑2倍）是因为自己已经被作为小的数的倍数考虑过（即2的3倍），因此每一个数都从自身倍数开始直到n。

代码如下：

public class Solution {
    public int countPrimes(int n) {
        boolean[] isPrime = new boolean[n];
        for (int i = 0; i < n; i++) {
            isPrime[i] = 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;
    }
}