作法:線性篩法(就跟題目的敘述差不多意思)

/**********************************************************/

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
char num[10000001]={0};
int map[10000001]={0};
main()
{
 int a,b;
 for(a=2;a<10000001;a++)
  {
   if(num[a]==0)
    {
      for(b=2;b<10000000;b++)
       if(a*b>10000000) break;
       else num[a*b]=1;
      map[a]=1;
    } 
    map[a]+=map[a-1];
  }
  int n,m;
  int t;
  scanf("%d",&t);
 while(t--)
   {
     scanf("%d %d",&n,&m);
     int temp=abs(map[m]-map[n]);
     if(m>n)
      {
        if(map[n]>map[n-1]) temp++;
      }
     else       
     {
        if(map[m]>map[m-1]) temp++;
      }
     printf("%d\n",temp);
   } 
 return 0;
}