摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法 : 建表 之後頭減尾直接得個數 (DP)

應該還有更快的方法 待補ˇ

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

#include<stdio.h>
#include<stdlib.h>
int input()     
{     
  char cha;     
  int x=0;     
  while(cha=getchar())     
     if(cha!=' '&&cha!='\n') break;     
  x=cha-48;     
  while(cha=getchar())      
    {     
     if(cha==' '||cha=='\n') break;     
      x=x*10+cha-48;     
    }     
    return x;     
}
short int DP[1000001]={0};
char num[1000001]={0};
int DigitPrimes()
{
  int a,b,c;
  for(a=2;a<1000000;a++)
     {
      DP[a]=DP[a-1];
      if(num[a]==0&&(a%2!=0||a==2))
        {
           if(a<1000)
             for(b=3;a*b<1000000;b=b+2)
                num[a*b]=1;
           int s=0,n=a;
           while(n)
              {
                s+=(n%10);
                n/=10;
              }
            if(num[s]==0&&(s%2!=0||s==2)) DP[a]++;
        }
     }
}
main()
{
 DigitPrimes();
 int t,t1,t2;
 scanf("%d",&t);
 while(t--)
     {
       t1=input();t2=input();
       printf("%d\n",DP[t2]-DP[t1]+(DP[t1]!=DP[t1-1]));
     }
 return 0;
}