#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

const int MAX=1000001;

bool nums[MAX];
int indexes[MAX];

void eraosthenes()
{
    int n=sqrt((double)MAX);
    for(int i=2; i<=n; i++)
    {
        int pos=i*i;
        while(pos<MAX)
        {
            nums[pos]=true;
            pos+=i;
        }        
    }
}

void createIndexes()
{
    eraosthenes();
    int i,k=1;
    for(i=2; i<MAX; i++)
        if (nums[i]==false) indexes[i]=k++;
    
    int m=MAX/2;
    for(i=2; i<=m; i++)
    {
        if (nums[i]==false)
        {
            int pos=2*i;
            while(pos<MAX)
            {
                indexes[pos]=indexes[i];
                pos+=i;
            }
        }
    }
}

bool run()
{
    int n;
    if (scanf("%d",&n)==EOF) return false;
    printf("%d\n",indexes[n]);
    return true;
}

int main()
{
    createIndexes();
    while(run());
    return 0;
}

HDU 2136 Largest prime factor 参考代码