10533 - Digit Primes

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

#define M 1000000
#define MH M/2
char prm[M/16+10];
long int prime[80000];
long int digPrmCnt[M];

void seive();
int isPrime(int);
int digSum(int);
void genDigPrm();
void cntDigPrm();

int main()
{
    int t,m,n;
   // freopen("in.txt","r",stdin);
    scanf("%d",&t);
   
    seive();
    genDigPrm();
    cntDigPrm();

    while(t--)
    {
        scanf("%d %d",&m,&n);
        printf("%d\n",digPrmCnt[n]-digPrmCnt[m-1]);
    }
    return 0;
}


void seive()
{
    int lim = (int)sqrt(M),i,j;
    for ( i = 3; i <= lim; i += 2){
        if ( !(prm[i>>4]&(1<<((i>>1)&0x7))) )
        {
            for (j = i*i/2; j <= MH; j+=i) prm[j>>3] |= (1<<(j&0x7));
        }
    }
}

int isPrime(int n)
{
    if ( n < 2) return 0;
    if ( n == 2) return 1;
    if ( n%2 == 0) return 0;
    if ( !(prm[n>>4]&(1<<( (n>>1)&0x7))) ) return 1;
    return 0;
}

int digSum(int n)
{
    int sum=0;
    while(n)
    {
        sum=sum+n%10;
        n=n/10;
    }
    return sum;
}

void genDigPrm()
{
    int i,j,dig;
    prime[0]=2;
    for(i=3,j=1;i<=1000000;i+=2)
        if(isPrime(i))
        {
            dig=digSum(i);
            if(isPrime(dig))
            {
                    prime[j]=i;
                    j++;
            }
        }
}

void cntDigPrm()
{
    int i,j=0,k=0;
    for(i=0;i<=M;i++)
        if(i==prime[j])
        {
            digPrmCnt[i]=++k;
            j++;
        }
        else
            digPrmCnt[i]=k;
}