 # Digit Primes

I am stuck in this problem. Pls help me out.
Here is the problem :-

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

Precompute a boolean array of size 100, in which `A[i]` is true if `i` is prime.
Create an array `B` of length `n`, and initialize it as 0.
Now, `for i in range(n):`
Compute the digit sum of `i`, and check if it’s prime. If it’s prime `B[i] = 1`.
This can be done in log_{10}i

Now make the prefix sum for `B`, and answer the queries in O(1).

4 Likes

What’s the use of prefix sum here. And what is n that you have used

n = 1000000.
Prefix sum is to answer queries in O(1).
Some pseudocode:

``````int prefix[n];
prefix = b;
for (int i = 1; i < n; ++i) prefix[i] = prefix[i-1]+b[i];
``````

``````int t1, t2;