欧拉线筛

#include<bits/stdc++.h>

using namespace std;

int prime[5800000],ans; bool vis[100000000];

int main()

{

int a;

cin>>a;

int cnt=0;

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

{

　　　　if(!vis[i])

　　　　　　{

　　　　　　prime[++cnt]=i;

　　　　　　}

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

　　　　{

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

　　　　　　if(i%prime[j]==0)

　　　　　　　　break;

　　　　}

}

　　printf("%dn",cnt);

}