題目來源
Count the number of prime numbers less than a non-negative number, n.
計(jì)算小于n的整數(shù)里有多少個質(zhì)數(shù)概页。我一開始想著直接算闲勺！如下：
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;
}
};
然后果然超時了…然后我也想不到別的方法了，只能看看討論區(qū)忘晤。
設(shè)置一個大小為n的數(shù)組來標(biāo)記i是否為質(zhì)數(shù)趁俊，當(dāng)遍歷到n的時候，把所有n的倍數(shù)的數(shù)字都標(biāo)記為非質(zhì)數(shù)。
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來減少運(yùn)行時間辐赞，比如說除了2之外，只考慮奇數(shù)硝训，如下：
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;
}
};
