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;
    }
}

results matching ""

    No results matching ""