CMED204-Editorial

editorial
1

PROBLEM LINK

Practice

DIFFICULTY:

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[0] = prefix[1] = 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; 
}