Hints:

store prime numbers in an vector;

then check the n-*it is prime or not

for example

6

2 4

3 3

here 2 is prime but (6-2)=4 is not prime

in the case of 3+3 here 3 is a prime and n-3=3 is also a prime number

## View Code

#include<bits/stdc++.h>

using namespace std;

const int N=10000005;

bool status[N];

#define ll long long

vectorprime;void sieve()

{

memset(status,0,sizeof status);

status[0]=status[1]=1;

ll k=N/2;for(ll i=2;i<=k;i++)

{

if(!status[i])

{

prime.push_back(i);

for(ll j=2*i;j<=N;j+=i) status[j]=1; } } } int main() { sieve(); ll t,n,co=0,cs=1; //ll dp[N]; cin>>t;

while(t–)

{

cin>>n;co=0;

ll k=n/2;

for(vector::iterator it=prime.begin();it!=prime.end() && *it<=k;it++)

{

if(status[n-*it]==0)

co++;

}

printf(“Case %lld: %lld\n”,cs++,co);

}

}

Advertisements