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

1 Like
#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 and i is also 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).

7 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';
7 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

#9

We haven’t used array A which we were created earlier.
And this Algorithm is not working…

#10

This should have been

for each prime i less than n:

Using Prime Sieve will save a lot of time here.

#11

You use the array A to check if a number is prime. I assumed that was fairly obvious to mention.

#12

You are right. Checking it just for prime numbers would save a lot of time.

#14

Don’t Know what is the bug in this code? Please help me out…

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6;

int main() {
int A[100] = {0};
int B[1000000] = {0};

for(int i = 2; i <= 100; i++) { 
	int count = 0;
	for(int j = 1; j*j <= i; j++) {
		if(i%j == 0)
			count += 2;
	}
	if(count == 2) {
		A[i] = 1;
	}
}
for(int i = 2; i <= N; i++) {
	int n = i;
	int sum = 0;
	while(n != 0) {
 		sum += n%10;
 		n /= 10;
 	}
	if(A[sum] == 1 && A[i] == 1)
		B[i] = 1;
}
int prefix[N];
prefix[0] = B[0];
for(int i = 1; i <= N; i++) {
	prefix[i] = prefix[i-1] + B[i];
}

int t; scanf("%d", &t);
while(t--) {
	int t1, t2; scanf("%d %d", &t1, &t2);
	if(t1 != 1)
		printf("%d\n", (prefix[t2-1]-prefix[t1-2]));
	else
		printf("%d\n", prefix[t2-1]);
}

}

#15

@sarfraj_123 Here’s the code with an explanation

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

// Function to compute Sum of Digits
int sumOfDigits(int n) { 
    int s = 0;
    while(n > 0) {
        s += n % 10;
        n /= 10;
    }
    return s;
}

// Precalculates all Prime Digits below 1 Million

int* preCompute() {
    
    int size = 1000001;
    // Array of Size 1 Million
    int prime[size];
    
    
    // Sieve Logic follows
    prime[0] = 0;
    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
            }
        }
    }
    
    // Uncomment these lines to check the primes less than 100
    // for(int i = 1; i <= 100; i++) {
    //     if(prime[i])
    //         fprintf(stderr, "%d ", i);
    // }
    // fprintf(stderr, "\n");
    
    
    // If i is prime and sum of digits of i is prime as well
    for(int i = 3; i < size; i += 2) {
        prime[i] = (prime[i] & (prime[sumOfDigits(i)]));
    }
    
    // Uncomment these lines to check Digit Primes less than 100
    // for(int i = 1; i <= 100; i++) {
    //     if(prime[i])
    //         fprintf(stderr, "%d ", i);
    // }
    // fprintf(stderr,"\n");
    
    // Building Prefix Sum
    for(int i = 1; i < size; i++) {
        prime[i] += prime[i - 1];
    }
    
    int *prefix = prime;
    
    return prefix;
}

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

It seems the Sample Output for the given Sample Input is wrong.

Edit: Got my mistake. The sample output is correct.

1 Like
#16

okay Thank you

#17

It is showing Wrong Answer for this code too…

https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=9

#18

Can you paste the code as well as the problem statement here?

#19

Extremely Sorry!!!
The following should work

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

// Function to compute Sum of Digits
int sumOfDigits(int n) { 
    int s = 0;
    while(n > 0) {
        s += n % 10;
        n /= 10;
    }
    return s;
}

// Precalculates all Prime Digits below 1 Million

int* preCompute() {
    
    int size = 1000001;
    // Array of Size 1 Million
    int prime[size];
    
    
    // Sieve Logic follows
    prime[0] = 0;
    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
            }
        }
    }
    
    // Uncomment these lines to check the primes less than 100
    // for(int i = 1; i <= 100; i++) {
    //     if(prime[i])
    //         fprintf(stderr, "%d ", i);
    // }
    // fprintf(stderr, "\n");
    
    
    // If i is prime and sum of digits of i is prime as well
    
    int digitprime[size];
    
    digitprime[0] = 0;
    digitprime[2] = 1;
    
    for(int i = 3; i < size; i += 2) {
        digitprime[i] = prime[i] & prime[sumOfDigits(i)];
    }
    
    // Uncomment these lines to check Digit Primes less than 100
    // for(int i = 1; i <= 100; i++) {
    //     if(prime[i])
    //         fprintf(stderr, "%d ", i);
    // }
    // fprintf(stderr,"\n");
    
    // Building Prefix Sum
    for(int i = 1; i < size; i++) {
        digitprime[i] += digitprime[i - 1];
    }
    
    int *prefix = digitprime;
    
    return prefix;
}

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

What went wrong?

We have overridden previous values. Because of which 13 is not a digit prime and also marked as not prime (it shouldn’t have been), because of which 67 was also marked as not a digit prime (it shouldn’t have been). This could have gone so far making unwanted things.

1 Like
#20

Thank you very much
Could please explain the Algorithm in a few steps…

#21

Why it is still getting WA…