HDU4548+素数

简单题。

 /*

 */

 #include<stdio.h>

 #include<string.h>

 #include<stdlib.h>

 #include<algorithm>

 #include<iostream>

 #include<queue>

 #include<stack>

 #include<math.h>

 #include<map>

 using namespace std;

 const int maxn = ;

 int IsPrime[ maxn ],IsSpecialPrime[ maxn ];

 int GetSum( int x ){

     int ans = ;

     while( x ){

         ans += x%;

         x/=;

     }

     return ans;

 }

 void init_prime(){

     for( int i=;i<maxn;i+= )

         IsPrime[i] = ;

     for( int i=;i<maxn;i+= )

         IsPrime[i] = ;

     IsPrime[] = ;

     IsPrime[] = ;

     for( int i=;i<maxn;i++ ){

         if( IsPrime[i]== ){

             int t,delta;

             delta = i*;

             t = delta+i;

             while( t<maxn ){

                 IsPrime[t] = ;

                 t += delta;

             }

         }

     }

     //for( int i=maxn-1;;i-- ){

         //if( IsPrime[i]==1 ){

             //printf("max=%d\n",i);

             //break;

         //}

     //}

     //memset( IsSpecialPrime,0,sizeof(IsSpecialPrime) );

     for( int i=;i<maxn;i++ ){

         if( IsPrime[i]==&&IsPrime[GetSum(i)]== ){

             IsSpecialPrime[i] = ;

         }

         else{

             IsSpecialPrime[i] = ;

         }

     }

     for( int i=;i<maxn;i++ )

         IsSpecialPrime[ i ] += IsSpecialPrime[ i- ];

 }

 int main(){

     init_prime();

     int ca;

     scanf("%d",&ca);

     int T = ;

     while( ca-- ){

         printf("Case #%d: ",T++);

         int L,R;

         scanf("%d%d",&L,&R);

         printf("%d\n",IsSpecialPrime[R]-IsSpecialPrime[max(,L-)]);

     }

     return ;

 }