学步园

#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;

const int N=1000001;
int f[N];

int main()
{
    int n;
    int i,j;
    int t=0;
    memset(f,0,sizeof(f));
    for(i=2; i<N; i++)
    {
        if(!f[i])//筛出素数
        {
            t++;
            for(j=i; j<N; j+=i)
            {
                f[j]=t;//最大素数覆盖
            }
        }
    }
    while(~scanf("%d",&n))
    {
        printf("%d\n",f[n]);
    }
    return 0;
}