Digit Primes

help
#1

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

#2

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
#3

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

#4

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

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

To answer each query:

int t1, t2;
cin >> t1 >> t2;
if (t1 != 1) cout << prefix[t2-1]-prefix[t1-2] << '\n';
else cout << prefix[t2-1] << '\n';
6 Likes
#5

Ohh i understood now. Thanx.

1 Like
#6

t1 and t2 <= 1000000 so how does only computing for first 100 prime numbers work ?

#7

The sum of the digits of any (prime) number within the range allowed is less than 100. So for each prime number, calculate the sum of its digits, and see immediately if this sum is a prime by looking in the boolean array.

1 Like
#8

Thank You Sir