//朴素低等高效算法
#include<stdio.h>
#include<math.h>
#include<time.h>
char tag[100000001];
void main()
{ unsigned long n,i,j,Num = 0,k,l;
clock_t start,finish;
scanf("%lu",&n);
start=clock();
k=sqrt(n);
for (i = 3; i <= k; i = i + 2)
if(tag[i>>1]==0)
{for (j = i * i; j <= n; j += i<<1)
tag[j>>1]=1;
}
//记录素数个数
j=n>>1;
for (i = 0; i < j; i++)
if (tag[i] == 0 )
{Num++;//printf("%lu ",(i<<1)+1);//打印素数
}
finish=clock();
printf("number=%lu time=%ld",Num,finish-start);
}