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

#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;
}