10533 Digit Primes-wRvsqaH5.txt

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
char ara[1000001]={0};
int dig[1000001]={0};
int sum_of_digit( int num)
{
    int sum=0;int temp;
    while(num!=0){
        temp = num%10;
        sum+=temp;
        num/=10;
    }
    return sum;
}
void Pgenerate()
{
    ara[0]=ara[1]=1;int p=0;
    dig[2]=(++p);
    for(int i=4; i<=1000000; i+=2)
        ara[i]=1;

    for(int i=3; i<=1000001; i+=2){
        if(ara[i]==0){
            for(int j = i+i; j<=1000001; j+=i)
                ara[j]=1;
            int x;
            x = sum_of_digit(i);
            if(ara[x]==0)
                dig[i]= (++p);
        }
    }
}
int main()
{
    Pgenerate();
    int test;scanf("%d",&test);
    int a,b;
    for(int v=1; v<= test; v++){
        scanf("%d%d",&a,&b);
        int s=0,t=0;int ans=0;
        int i,j;
        if(a==b){
            if(dig[a]>0){
                ans=1;
            }
        }
        else{
            int flag=0;
            if(a>b){
                swap(a,b);
                flag=1;
            }
            for( i=a; i<=b; i++){
                if(dig[i]>0){
                    s=dig[i];
                    break;
                }
            }
            for( j=b; j>=a; j--){
                if(dig[j]>0){
                    t=dig[j];
                    break;
                }
            }
            if(s==0 && t==0)
                ans=0;
            else
                ans = t-s+1;
            if( i==j&&dig[i]>0)
                ans=1;
            if(flag==1)
                ans*=(-1);
        }
        printf("%d\n",ans);
    }
}