204. 计数质数
- 暴力
- 筛选法，对所有数进行标记，对于一个质数，他所有的倍数都不是质数。
class Solution {
public:
int countPrimes(int n) {
if(n<3) return 0;
vector<int> res(1,2);
for(int i=3;i<n;i++)
{
int j;
for(j=0;j<res.size()&&res[j]*res[j]<=i;j++)
{
if(i%res[j]==0)
break;
}
if(j==res.size()||res[j]*res[j]>i)
res.push_back(i);
}
return res.size();
}
};