https://www.codechef.com/LRNDSA05
I was able to solve this problem with given constraint but how to solve it if N is of order 10^6 or greater
#include<bits/stdc++.h>
using namespace std;
vector <long> V(201,0);
vector <long> s_prime(201,0);
//mark all the primes upto n
void sieve()
{
V[0]=1;
V[1]=1;
for(long i=2;i*i<=200;i++)
{
for(long j=i*i;j<=200;j+=i)
V[j]=1;
}
}
//mark all the semi prime numbers upto n
void fun()
{
for(long i=6;i<=200;i++)
{
long c=0;long temp;
for(long j=2;j*j<=i;j++)
{
if(i%j==0)
{
temp=j;
c++;
}
}
if(c==1)
{
if(temp==i/temp)
continue;
else
{
if(V[temp]==0 && V[i/temp]==0)
s_prime[i]=1;
}
}
}
}
int main()
{
long t;
cin>>t;
sieve();
fun();
for(long i=0;i<t;i++)
{
long n;
cin>>n;long f=0;
//check if the number is sum of any two semi primes
for(long j=6;j<=n;j++)
{
if(s_prime[j]==1&& (s_prime[n-j]==1))
{
f=1;
break;
}
}
if(f==0)
cout<<"NO"<<endl;
else
cout<<"YES"<<endl;
}
return 0;
}