线性素数筛（欧拉筛）（超级好的MuBan）

Problem：找出小于等于n的所有素数的个数。

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e6;

int prime[maxn];  // 欧拉线性素数筛,O(n)

bool vis[maxn];   // 标记

int Prime(int n)

{

    memset(vis,false,sizeof(vis));

    int cnt = 0;

    vis[0] = vis[1] = true;

    for(int i = 2; i <= n; i ++)

    {

        if(!vis[i])prime[cnt++] = i;

        for(int j = 0; j < cnt && i*prime[j] <= n; j ++)

        {

            vis[i*prime[j]] = true;

            if(!(i%prime[j])) break;

        }

    }

    return cnt;

}

int main()

{

    int n;

    cin >> n;

    int ans = 0;

    ans = Prime(n);

    cout << ans << endl;

    return 0;

}