Super Primes

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;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro