10533 - Digit Primes

Author: Ismail Hosen

Daffodil International University

Problem Link

//Please follow from main function

#include<stdio.h>

#include<math.h>

#define MAX 1000001

int N = 1000000;

int status[MAX];

int state[MAX];

void seive()

{

    int i, j, root;

    status[0]=status[1]=1;

    status[2]=0;

    for(i=4; i<=N; i+=2) status[i]=1;

    root = sqrt(N );

    for( i = 3; i <= root; i += 2 )

    {

        if( status[i] == 0 )

        {

            for( j = i * i; j <= N; j += i + i )

                status[j] = 1;

        }

    }

}

int sum(int m)

{

    int j=0;

    while(m!=0)

    {

        j+=(m%10);

        m/=10;

    }

    return j;

}

void digit()

{

    int i, count=0;

    for(i = 0; i<=1000000; i++)

    {

        if(status[i]==0 && status[sum(i)]==0){

                count++;

        }

        state[i] = count;

    }

}

int main()

{

    int n, a, b, j;

    seive();

    digit();

    scanf("%d", &n);

    while(n--)

    {

        scanf("%d %d", &a, &b);

        j=state[b]-state[a-1];

        printf("%d\n", j);

    }

    return 0;

}