Digit Primes

help
22

Are you sure about this?
I explained the logic in the code :roll_eyes:.

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
23

Is it? :exploding_head:

24

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 :smiling_face_with_three_hearts:

Here is it…

25

I want to connect to you over social media.
Send me your linkedin link.
You are a gem for CP.

26

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

27

But this will not let me sleep.

1 Like
28

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[2] = 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[2] = 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
29

Thank you very much

30

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