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';
2 Likes
#5

Ohh i understood now. Thanx.

1 Like