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