# Digit Primes

I explained the logic in the code .

Anyways, doing what is asked is enough. Here is the solution in words.

The Question:

• A digit prime is a prime number whose sum of digits is also a prime. Find the number of digit primes in the given range (inclusive)

The Solution:

• First, run sieve over 1 Million to filter prime numbers. Sieve of Eratosthenes or Sieve of Sundaram aim for the same → To find all primes less than or equal to a given integer N (in this case, 1 Million).

• Now that we have all primes below 1 Million. We have to filter them further. To do that, we iterate over the primes, check if the sum of digits of i^{th} prime is also a Prime Number.
Example: 13 is a prime. But the sum of digits, viz., 1 + 3 = 4, is not a prime. So, 13 is not a Digit Prime
Another Example: 67 is a prime and sum of digits, viz., 6 + 7 = 13 is also a prime. So, 67 is a Digit Prime.

• Our task is to filter all such Primes below 10^6.

• The 2nd loop does the same thing.
`digitprime[i] = prime[i] & prime[sumOfDigits[i]];`
This statement returns 1 if i is a Prime and the sum of digits of i is a prime as well. Otherwise, it returns 0.

• Now, digitprime[i] = 1 if i is a digit prime else 0.

• In order to answer the queries efficiently, we make use of Prefix Sum.

• Say, you have to count the number of i's in the range [a, b] where digitprime[i] is 1. To do that, prefix sum is used.

• Prefix sum is an Array that stores the sum of values in a prefix of the Array.

• Say our digitprime array is:
[0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, ...] that corresponds to
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11],
which means, 2, 3, 5, 7, 11, ... are digit primes.

• The Prefix Sum looks like:
[0, 0, 1, 2, 2, 3, 3, 4, 4, 4, 4, 5, \dots] for
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, \dots]
There are 4 digit primes below 10, 5 digit primes less than or equal to 11 etc.
Formally, `prefix[i]` denotes the number of digit primes less than or equal to i.

• Using basic math, the number of Digit Primes in the range [a, b] is given by
`prefix[b] - prefix[a - 1]`.

This is the best I could explain.

3 Likes

Is it? Yeah, But hats off to your efforts to make the code understand better.
Thanks a lot. I never forget this question.
I want this type of Editorial Here is it…

I want to connect to you over social media.
You are a gem for CP.

On My Github Profile Page, you can find link to my LinkedIn Profile.

But this will not let me sleep.

1 Like

Finally, got it ACfied.

C Code
``````/*
* Author: Chitturi Sai Suman
* Date: 2021-05-21
*/
#include <stdio.h>
#include <stdlib.h>

#define size 1001000

int prime[size] = {0};

int digitprime[size] = {0};

int sumOfDigits(int n) {
int s = 0;
while(n > 0) {
s += n % 10;
n /= 10;
}
return s;
}

// Precalculates all Prime Digits below 1 Million

void preCompute() {

prime = 1; // 2 is the only even prime

for(int i = 3; i < size; i += 2) {
prime[i] = 1; // Assume every odd number as prime
}

for(int i = 3; i * i < size; i += 2) {
if(prime[i]) {
for(int j = i * i; j < size; j += i) {
prime[j] = 0; // Multiples of Primes are marked as Not Prime
}
}
}

digitprime = 1;

for(int i = 3; i < size; i += 2) {
digitprime[i] = prime[i] & prime[sumOfDigits(i)];
}
for(int i = 1; i < size; i++) {
digitprime[i] += digitprime[i - 1];
}
}

int main() {
preCompute();
int t;
scanf("%d", &t);
for(; t > 0; t--) {
int a, b;
scanf("%d %d", &a, &b);
printf("%d\n", digitprime[b] - digitprime[a - 1]);
// Print result in O(1) per test case.
}
return 0;
}
``````
2 Likes

Thank you very much

Yes, I too got AC.
Thank you…
I thought of doing in this manner by using the global array.
Thank you.
It is glad to meet you today.

1 Like