QUESTION

A prime number is Super Prime if it is a sum of two primes. Find all the Super Primes upto N\n\nInput:\n\nThe first line of input contains an integer T denoting the number of test cases.\n\nEach line of test case contains an integer N as described in the problem\n\nOutput:\n\nFor each test case output a single line containing the total number of Super Primes upto N.\n\n\nConstraints:\n\n1<=T<=10000\n\n1<=N<=10000000.

ANSWER

#include<bits/stdc++.h>
using namespace std;
bool SieveOfEratosthenes(int n, bool isPrime[])
{
	isPrime[0] = isPrime[1] = false;
	for (int i=2; i<=n; i++)
		isPrime[i] = true;

	for (int p=2; p*p<=n; p++)
	{
		if (isPrime[p] == true)
		{
			for (int i=p*2; i<=n; i += p)
				isPrime[i] = false;
		}
	}
}
void superPrimes(int n)
{
	bool isPrime[n+1];
	int cnt=0;
	SieveOfEratosthenes(n, isPrime);
	int primes[n+1], j = 0;
	for (int p=2; p<=n; p++)
	if (isPrime[p])
		primes[j++] = p;

	for (int k=0; k<j; k++)
		if (isPrime[k+1] && primes[k]<n)
		{
		    cnt++;
		}
			cout << cnt<<endl;
}

int main()
{
	int n,t;
	cin>>t;
	while(t)
	{
	    cin>>n;
	   
	superPrimes(n);
	t--;
	}
	return 0;
}