算法思想
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]);
}
}
