Sol：筛法求素数打表时预处理下即可。
#include <cstdio>
#include <cstring>
using namespace std;
const int maxisp = 1000000 + 10;
const int maxp = 1000000 + 10;
int num,n;
int prime[maxp];
int isprime[maxisp];
inline void get_prime()
{
num=1;
for(int i=2;i<=maxisp;i++)
if(!isprime[i])
{
prime[i]=num++;
for(int j=1;j*i<=maxisp;j++)
{
isprime[i*j]=1;
prime[i*j]=prime[i];
}
}
}
int main()
{
prime[1]=0;
get_prime();
int N;
while(~scanf("%d",&N))
printf("%d\n",prime[N]);
return 0;
}