欧拉筛

现学现卖，哔哩哔哩搜“欧拉筛选”后写的

#include <bits/stdc++.h>
using namespace std;
int vis[2000010];
int pri[2000010];

int main()
{
    int n=10000,m=0,cnt=0;
    cin>>n;
    for(int i=2;i<=n;i++)
        {
            if(vis[i] == 0)pri[cnt++] = i;
            for(int j=0;j<=cnt;j++)
                {
                    if(pri[j]*i>n )break;
                    vis[pri[j]*i] = 1;
                    if(i%pri[j]==0)break;
                }
        }
    cout<<cnt;
    return 0;
}