我觉得assiss的程序还可以优化一下:
#include <stdio.h>
#define N 1000000
char s[N+1];
int main(int argc,char** argv)
{
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<=N/2;i+=2)
{
if(s[i])continue;
for(n=3*i;n<=N;n+=2*i) //优化就在本行,应该可少循环 10 0000 次。
{
s[n]=1;
}
}
for(i=2,n=0;i<=N;i++)
{
if(s[i]==0)
{
//printf("%d\n",i);//如果把这个数打印出来,会花很长的时间。为了方便起见,所有的程序我在测试时间时都会把打印这条去掉。
n++;
}
}
printf("%d\n",n);
return 0;
}