#include<stdio.h>
#include<math.h>

#define MAX 1000000

int main(void)
{
    int i,j,a,b,cnt,gap,prime,is_prime,len=0;
    int arr[MAX];
   
    arr[len++]=2; arr[len++]=3; arr[len++]=5;   //取6的倍數 6k+1,6k+5
    gap=2; prime=7;
   
    while(scanf("%d %d",&a,&b)==2) {
      if(a==1) a++;
     
      for(i=0;i<len && arr[i]<a;i++) ;
      for(cnt=0;i<len && arr[i]>=a && arr[i]<=b;++cnt,i++) ;
     
      for(;prime<=b;prime+=gap) {
        for(is_prime=1,j=2;arr[j]<=(int)sqrt(prime) && is_prime;j++)
           if(prime%arr[j]==0)
              is_prime=0;                       
       
       
        if(is_prime) {
          arr[len++]=prime;
          ++cnt;            
        }
              
        gap=6-gap;                                          
      }                 
     
      for(;i<len && arr[i]<a;--cnt,i++) ;
      printf("%d\n",cnt);                        
    }                
   
   
    return 0;
}

這樣寫太難讓人看懂了!!

預先建質數表

不然每詢問一次a,b都要重新建質數表

這樣太久了

prime這個變數儲存目前執行所得的最大質數,若測資要求的範圍小,則進不了尋找的迴圈,若超過prime目前值,則進行尋找的動作,應該有排除一些不必要的每個測資都從頭執行尋找的動作,不至於執行過時吧!