10533 - Digit Primes

[lighted]

You could read this thread before posting.

Make precomputation in range 1..1000000 of all primes and sum of their digits using sieve of eratosthenes. Save in boolean array which of them is digit prime or not. Then precompute in array sum[1000001] number of digit primes, such that sum = number of digit primes between 1 and i. Then process input. Using this array you can get answer in O(1). For each input t1 and t2 answer is sum[t2] - sum[t1 - 1].

By the way, sum of digits of a number can be also calculated using sprintf without making division and mod operations.

[bgcsaif]

I am tired of TLE for this problem.... First I tried it manual then I tried it with sieve method..... But yet I am having TLE.... Help me to with any clues plz.....
http://ideone.com/uTTQz8

[bgcsaif]

Is there anyone? I need help....

[oja]

Make an array(let's say "arr") that stores the number of digit primes up to the value of the index. For example, arr[10] contains the number of digit primes
from 0 to 10. Fill this array before processing any input. Check if 0 is digit prime. It isn't. So arr[0] is 0. Next is 1. It isn't either so arr[1] = arr[0] + 0 = 0 + 0 = 0.
Next is 2. It is, so arr[2] = arr[1] + 1 = 0 + 1 = 1. Then 3. It is digit prime. So arr[3] = arr[2] + 1 = 1 + 1 = 2. Do this up to the maximum upper limit. Use sieve of
eratosthenes to check for primality.

Now given an interval a and b, how many digit primes are there?It's just arr - arr[a - 1]. This is much faster and more efficient than counting the number of digit
primes from a to b for every query.