简单题。
1 /* 2 3 */ 4 #include<stdio.h> 5 #include<string.h> 6 #include<stdlib.h> 7 #include<algorithm> 8 #include<iostream> 9 #include<queue> 10 #include<stack> 11 #include<math.h> 12 #include<map> 13 using namespace std; 14 const int maxn = 1000005; 15 int IsPrime[ maxn ],IsSpecialPrime[ maxn ]; 16 int GetSum( int x ){ 17 int ans = 0; 18 while( x ){ 19 ans += x%10; 20 x/=10; 21 } 22 return ans; 23 } 24 25 void init_prime(){ 26 for( int i=1;i<maxn;i+=2 ) 27 IsPrime[i] = 1; 28 for( int i=0;i<maxn;i+=2 ) 29 IsPrime[i] = 0; 30 IsPrime[1] = 0; 31 IsPrime[2] = 1; 32 for( int i=3;i<maxn;i++ ){ 33 if( IsPrime[i]==1 ){ 34 int t,delta; 35 delta = i*2; 36 t = delta+i; 37 while( t<maxn ){ 38 IsPrime[t] = 0; 39 t += delta; 40 } 41 } 42 } 43 //for( int i=maxn-1;;i-- ){ 44 //if( IsPrime[i]==1 ){ 45 //printf("max=%d ",i); 46 //break; 47 //} 48 //} 49 //memset( IsSpecialPrime,0,sizeof(IsSpecialPrime) ); 50 for( int i=0;i<maxn;i++ ){ 51 if( IsPrime[i]==1&&IsPrime[GetSum(i)]==1 ){ 52 IsSpecialPrime[i] = 1; 53 } 54 else{ 55 IsSpecialPrime[i] = 0; 56 } 57 } 58 for( int i=1;i<maxn;i++ ) 59 IsSpecialPrime[ i ] += IsSpecialPrime[ i-1 ]; 60 } 61 int main(){ 62 init_prime(); 63 int ca; 64 scanf("%d",&ca); 65 int T = 1; 66 while( ca-- ){ 67 printf("Case #%d: ",T++); 68 int L,R; 69 scanf("%d%d",&L,&R); 70 printf("%d ",IsSpecialPrime[R]-IsSpecialPrime[max(0,L-1)]); 71 } 72 return 0; 73 }