UVa - 10533 - Digit Primes

Problem on UVa

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).

#include <cstdio>

#define N 1000000

bool primes[N+1];
int digitPrimes[N+1];

void sieve(void)
{
    for(int i = 0; i <= N; ++i)
    {
        primes[i] = true;
        digitPrimes[i] = 0;
    }

    primes[0] = primes[1] = false;

    for(int i = 2; i * i <= N; ++i)
    {
        if(primes[i])
        {
            for(int j = 2 * i; j <= N; j += i)
            {
                primes[j] = false;
            }
        }
    }

    int countDigPrimes = 0;

    for(int i = 2; i <= N; ++i)
    {
        if(primes[i])
        {
            int tmp = i;
            int sumDigits = 0;

            while(tmp)
            {
                sumDigits += tmp%10;
                tmp /= 10;
            }

            if(primes[sumDigits])
            {
                ++countDigPrimes;
            }
        }
        digitPrimes[i] = countDigPrimes;
    }
}

int main(int argc, char *argv[])
{
    int numLines;

    int t1, t2;

    sieve();

    scanf("%d", &numLines);

    for(int iLine = 0; iLine < numLines; ++iLine)
    {
        int numDigiPrimes;

        scanf("%d %d", &t1, &t2);

        if(t1 == 0)
            numDigiPrimes = digitPrimes[t2];
        else
            numDigiPrimes = digitPrimes[t2] - digitPrimes[t1 - 1];
        printf("%d\n", numDigiPrimes);
    }

    return 0;
}