break-word; clear: both; text-indent: 2em; color: rgb(24, 30, 51); font-family: PingFangSC, 微软雅黑, 黑体, Arial, Helvetica, sans-serif; font-size: 18px; background-color: rgb(255, 255, 255); line-height: 2;">【案例描述】

break-word; clear: both; text-indent: 2em; color: rgb(24, 30, 51); font-family: PingFangSC, 微软雅黑, 黑体, Arial, Helvetica, sans-serif; font-size: 18px; background-color: rgb(255, 255, 255); line-height: 2;">利用筛选法求[2,n](n<100)上的质数个数。

筛选法：删除最小数的m倍数(m>1)。如此重复，直到无数可删除。

【案例分析】

利用筛选法的基本思路是：

1、将[0,99]上的全部整数作上删除标记：int a[100]={1,1,0};

其中a[0]=1,a[1]=1，表示数0、1已删除。a[k]=0,k=2,3,...,99，表示数k未删除。

2、在[b,n]上查找未作删除标记的最小整数b（b的初值为2）：

（1）如果b未找到，转3

（2）在(b,n]上对b的倍数作删除标记

（3）b++，转2

3、输出[0,n]上未作删除标记的全部整数

【参考代码】

main()

{ int n,i,s=0,t,b=2,a[100]={1,1,0};

  scanf("%d",&n);

  while(1)

  {  for(i=b;i<n;i++)

         if(a[i]==0)break;

     if(i>n)break;

     t=i+i;

     while(t<=n){a[t]=1;t+=i;}

     b++;

  }

  for(i=2;i<=n;i++)

  if(a[i]==0)s++;

  printf("%d",s);}