/* g++ 3.2.2 linux */
#include <math.h>
#include <sys/time.h>
#include <stdio.h>
#define N 1000000
char s[N+1];
int main(int argc,char** argv)
{
timeval tv;
gettimeofday(&tv,0);
int i=0,j=0,n=0,k=0;
for(i=1;i<=N;i++)s[i]=0;
for(n=4;n<=N;n+=2)
{
s[n]=1;
}
for(i=3;i<=(int)sqrt((double)N);i+=2)//优化就在本行,从0.145秒提升到0.103秒
{
if(s[i])continue;
for(n=i*i;n<=N;n+=2*i)//再次优化就在本行,从0.103秒提升到0.950秒
{
s[n]=1;
}
}
timeval newtv;
gettimeofday(&newtv,0);
timersub(&newtv,&tv,&newtv);
printf("%d.%d\n",newtv.tv_sec,newtv.tv_usec);
for(i=2,n=0;i<=N;i++)
{
if(s[i]==0)
{
//printf("%d\n",i);//如果把这个数打印出来,会花很长的时间。为了方便起见,所有的程序我在测试时间时都会把打印这条去掉。
n++;
}
}
printf("%d\n",n);
return 0;
}