题目来源
Count the number of prime numbers less than a non-negative number, n.
计算小于n的整数里有多少个质数。我一开始想着直接算！如下：
class Solution {
public:
int countPrimes(int n) {
int res = 0;
if (n == 1)
return 0;
for (int i=2; i<n; i++) {
if (isPrimes(i))
res++;
}
return res;
}
bool isPrimes(int x)
{
for (int i=2; i<=x/2; i++) {
if (x % i == 0)
return false;
}
return true;
}
};
然后果然超时了…然后我也想不到别的方法了，只能看看讨论区。
设置一个大小为n的数组来标记i是否为质数，当遍历到n的时候，把所有n的倍数的数字都标记为非质数。
class Solution {
public:
int countPrimes(int n) {
vector<bool> noPrime(n, false);
int res = 0;
if (n == 1)
return 0;
for (int i=2; i<n; i++) {
if (noPrime[i-1] == false) {
res++;
for (int j=2; i*j<n; j++) {
noPrime[i*j-1] = true;
}
}
}
return res;
}
};
然后可以有各种trick来减少运行时间，比如说除了2之外，只考虑奇数，如下：
class Solution {
public:
int countPrimes(int n) {
vector<bool> noPrime(n, false);
int res = 1;
if (n <= 2)
return 0;
for (int i=3; i<n; i+=2) {
if (noPrime[i-1] == false) {
res++;
for (int j=2; i*j<n; j++) {
noPrime[i*j-1] = true;
}
}
}
return res;
}
};
