题目描述：

 

源码：

 需要注意，若使用cin，cout输入输出，会超时。

#include"iostream"#include"memory.h"#define MAX 1000000using namespace std;int index[MAX];int main(){		memset(index, -1, sizeof(index));	index[1] = 0;	int sum = 0;	for(int i = 2; i < MAX; i++)	{		if(index[i] == -1)		{			sum++;			for(int j = i; j < MAX; j+= i)			index[j]=sum;		}	}	int n;	while(scanf("%d", &n) != EOF)		printf("%d\n", index[n]);    return 0;}