# PROBLEM LINK:

* Author:* Naman Singh

*Adwita Arora*

**Tester:***Madhavi Dixit*

**Editorialist:**# DIFFICULTY:

EASY

# PREREQUISITES:

XOR logical operator, Sieve algorithm

# PROBLEM:

To find number of prime numbers in the given range such that the xor of their digits is a prime too.

# QUICK EXPLANATION:

In this problem, **l** and **r** being two integer values, such that the prime numbers lying within the range **[l,r]** must satisfy the condition such that the logical **XOR** operation of all the digits is also a **prime number**. We need to find the sum of these numbers in the given range.

# EXPLANATION:

The problem relies on the use of pre-computation. We will define an array called **csum[]** which at each index stores the sum of those primes satisfying the brief upto its corresponding whole number. The 0th element contains 0 since 0 is not prime.

As it is evident from the source code (given below), in the user defined function **sieve_generate**, every integer value (within the defined range) is checked whether it is prime or not, if the number is prime; true value is returned otherwise we get a false value.

Next, we run a loop for all whole numbers starting from 1 upto the maximum limit. Within the loop, the current index of **csum** stores in itself the preceding value of the array.

Next we determine whether the current whole number being considered satisfies the brief - being prime itself and having the **XOR** of its digits as prime. If true, then this number gets added to the current value of the **csum** array.

In this way each element of **csum** stores the sum of all eligible primes upto that index. The example below will further illustrate the problem:

Here we have taken a basic example where **l=1** and **r=10**. The boxes represent the **csum[]** array with each element written below its corresponding natural number. The numbers which are prime are written in green. Since they all have single digits they satisfy both prerequisites.

# SOLUTIONS:

## Setter's Solution

```
#include <bits/stdc++.h>
using namespace std;
#define MAX 1'00'005
bool is_prime[MAX];
void sieve_generate(){
for(int i=0; i<MAX; ++i){
is_prime[i] = (i&1);
}
is_prime[0] = is_prime[1] = false;
is_prime[2] = true;
for(int i=3; i*i<MAX; i+=2){
if(is_prime[i]){
for(int j=i*i; j<MAX; j+=2*i){
is_prime[j] = false;
}
}
}
}
int digits_xor(int num){
int ans = 0;
while(num){
ans ^= (num%10);
num /= 10;
}
return ans;
}
long long csum[MAX];
void init(){
sieve_generate();
csum[0] = 0;
for(int i=1; i<MAX; ++i){
csum[i] = csum[i-1];
// cout << i << " " << (is_prime[i] && is_prime[digits_xor(i)]) << endl;
if(is_prime[i] && is_prime[digits_xor(i)]){
csum[i] += i;
}
}
}
int main(){
init();
int t;
cin >> t;
while(t--){
int l, r;
cin >> l >> r;
cout << csum[r] - csum[l-1] << endl;
}
return 0; }
```