问题描述
Description:
Count the number of prime numbers less than a non-negative number, n.
问题分析
筛选法求素数，参考这篇文章【算法】普通方法和筛选法求素数，这道题用普通方法求素数会超时，只能用筛选法。
代码
class Solution {
public:
int countPrimes(int n) {
if(n<=1) return 0;
n--;
bool val[n];
for(int i=0;i<n;i++) {
val[i] = true;
}
val[0] = false;
for(int i=1;i<n;i++) {
if(val[i]==false) continue;
// 判断 i+1 是否为素数
int tmp = i+1;
bool isPrime = true;
for(int j=2;j*j<=tmp;j++) {
if(tmp%j==0) {
// 不是素数
isPrime = false;
break;
}
}
if(isPrime) {
// 将这个素数所有的倍数都设置为 false
for(int j=tmp+tmp;j<=n;) {
val[j-1] = false;
j+=tmp;
}
}
}
int count = 0;
for(int i=0;i<n;i++) {
if(val[i]) {
count++;
}
}
return count++;
}
};