地址

算法思想

1.初始化所有数都是素数
2.i从2开始循环，根号N结束
3.i的所有倍数都不是素数

算法流程图

以后补

AC代码

#include<iostream>
using namespace std;
#include<math.h>
#define OK 1
#define MAXSIZE 100000+5
typedef int Status;
typedef int ElementType;
typedef int KeyType;
int a[MAXSIZE];
Status prime()
{
    int count = 0;
    for(int i=2;i<MAXSIZE;i++)a[i]=1;
    for(int i=2;i<sqrt(MAXSIZE*1.0);i++) 
        if(a[i])
            for(int j=i<<2;j<MAXSIZE;j+=i) a[j]=0;
    for(int i=2,count=0;i<MAXSIZE;i++) a[i]?a[i]=++count:a[i]=count;
    return OK;
}
int main()
{
    prime();
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        printf("%d\n",a[n]);
    }
}