问题描述:统计所有小于非负整数 n 的质数的数量。
思路:大于2的偶数都不是质数,所以我们只需要判断奇数是不是质数。
代码如下:
public int CountPrimes(int n) {
if(n<3)
return 0;
int count=n/2;
bool[] f=new bool[n];
for(int i=3;i*i<=n;i+=2)
{
if(f[i])
continue;
for(int j=i*i;j<n;j+=2*i)
{
if(!f[j])
{
--count;
f[j]=true;
}
}
}
return count;
}