View Code
1 #include <stdio.h> 2 #include<math.h> 3 int prime[1000000]; 4 int main() 5 { 6 int s,max; 7 while(scanf("%d",&max)!=EOF&&max!=0) 8 { 9 s=0; 10 prime[0]=prime[1]=0;prime[2]=1; 11 for(int i=3;i<max;i++) 12 prime[i]=i%2==0?0:1; 13 int t=(int)sqrt(max*1.0); 14 for(int i=3;i<=t;i++) 15 if(prime[i]) 16 for(int j=i*2;j<max;j+=i) 17 prime[j]=0; 18 for(int i=2;i<=max;i++) 19 if(prime[i]==1) 20 s++; 21 printf("%d\n",s); 22 } 23 return 0; 24 }