Solution of 10533 - Digit Primes

Problem Description
source:https://uva.onlinejudge.org/external/105/10533.html

A prime number is a positive number, which is divisible by exactly two different integers. A digit prime is a prime number whose sum of digits is also prime. For example the prime number 41 is a digit prime because 4 + 1 = 5 and 5 is a prime number. 17 is not a digit prime because 1 + 7 = 8, and 8 is not a prime number. In this problem your job is to find out the number of digit primes within a certain range less than 1000000. 

Input 

First line of the input file contains a single integer N (0 < N ≤ 500000) that indicates the total number of inputs. Each of the next N lines contains two integers t1 and t2 (0 < t1 ≤ t2 < 1000000). 

Output 


For each line of input except the first line produce one line of output containing a single integer that indicates the number of digit primes between t1 and t2 (inclusive).

Sample Input

3 
10 20 
10 100 
100 10000 

Sample Output 

1 
10 
576 

Note: You should at least use scanf() and printf() to take input and produce output for this problem. cin and cout is too slow for this problem to get it within time limit. 

Solution:

#include <algorithm>
#include <cstdio>
#include <cmath>
#include <string>
#include <vector>
#include<stdio.h>
#include<stdlib.h>
#define max 1000002

using namespace std;

void GenPrime();
void DigitPrime();
long int prime[max];
long int dprime[max];

int main()
{
    GenPrime();
    DigitPrime();
    long int t,t1,t2,i,sum,n,j,total;
    //freopen("in.txt","r",stdin);
    while(scanf("%ld",&t)==1)
    {
        for(i=1;i<=t;i++)
        {
            scanf("%ld%ld",&t1,&t2);
            total=dprime[t2]-dprime[t1-1];
            printf("%ld\n",total);
        }
    }
    return 0;
}

void GenPrime()
{
    long int i,j,m;
    m=(long int)sqrt(max);
    memset(prime, 1, sizeof(prime));
    prime[0]=prime[1]=0;
    for(i=2;i<=m;i++)
    {
        if(prime[i])
        {
            for(j=i+i;j<max;j+=i)
                prime[j]=0;
        }

    }

}
void DigitPrime()
{
    long int n,i,nodprime,sum;
    nodprime=0;
    for(i=2;i<max;i++)
    {
        if(prime[i])
        {
            sum=0;
            n=i;
            while(n>9)
            {
                sum+=n%10;
                n/=10;
            }
            sum+=n;
            if(prime[sum])
                nodprime+=1;
        }
        dprime[i]=nodprime;
    }
}