埃氏筛法

求n以内素数个数

复杂度：O(nloglogn)

代码：

int prime[maxn]; //第i个素数
bool is_prime[maxn+1];//是否是素数

//返回n以内素数个数
int sieve(int n)
{
    int cnt = 0;
    for(int i = 0; i <= n; ++i) is_prime[i] = true;
    is_prime[0] = is_prime[1] = false;
    for(int i = 2; i <= n; ++i)
    {
        if(is_prime[i])
        {
            prime[cnt++] = i;
            for(int j = 2 * i; j <= n; j += i) is_prime[j] = false;//划去倍数
        }
    }
    return cnt;
}