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
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).
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.
@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.
/*
* 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.