Practice

EASY-MEDIUM

# PREREQUISITES:

MATHS , OBSERVATION

# EXPLANATION:

According to the question, we need to find the numbers of prime numbers which are the sum of other prime numbers, this is based on Goldbach’s conjecture. This says any prime number greater or equal to 5 can be represented as the sum of other prime numbers. So we need to find no of prime number in given range excluding 2 and 3 .

# SOLUTION:

``````#include <bits/stdc++.h>
#define int long long int
using namespace std;

const int MAX = 100000000;

// prefix[i] is going to store count of primes
// till i (including i).
int prefix[MAX + 1];

void buildPrefix()
{
// Create a boolean array "prime[0..n]". A
// value in prime[i] will finally be false
// if i is Not a prime, else true.
bool prime[MAX + 1];
memset(prime, true, sizeof(prime));

for (int p = 3; p * p <= MAX; p++) {

// If prime[p] is not changed, then
// it is a prime
if (prime[p] == true) {

// Update all multiples of p
for (int i = p * 2; i <= MAX; i += p)
prime[i] = false;
}
}

// Build prefix array
prefix = prefix = 0;
for (int p = 2; p <= MAX; p++) {
prefix[p] = prefix[p - 1];
if (prime[p])
prefix[p]++;
}
}

// Returns count of primes in range from L to
// R (both inclusive).
int query(int L, int R)
{
return prefix[R] - prefix[L - 1];
}

// Driver code
int32_t main()
{
buildPrefix();
int t;
cin>>t;
while(t-->0){
int L,R;
cin>>L>>R;
cout << query(L, R) << endl;
}
return 0;
}

``````