Question : Chef and primes
I try to solve the problem by precomputing all the semi primes and splitting the given number into two pairs and determining whether the two numbers are semi primes or not.
for finding the semi primes I used the sieve and prime factorization.
I’m able to pass all the pre-tests given in the problem but I’m getting the wrong answer after submitting it
my code :
#include<bits/stdc++.h>
using namespace std;
#define newline '\n'
#define ll long long
#define pi (3.141592653589)
#define MOD 1000000007
#define vi vector<int>
#define fastio ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
vi createSemiPrimes(int n)
{
vi values(n + 1);
for (int i = 1; i <= n;i++) values[i] = i;
vi countDivisions(n + 1);
for (int i = 1; i <= n;i++) countDivisions[i] = 2;
for (int i = 2;i <= n;i++)
{
if (values[i] == i && countDivisions[i] == 2)
{
for (int j = 2 * i;j <= n;j += i)
{
if (countDivisions[j] > 0)
{
values[j] /= i;
countDivisions[j]--;
}
}
}
}
vi result(n + 1);
for (int i = 2;i <= n;i++)
{
if (values[i] == 1 && countDivisions[i] == 0)
{
result[i] = 1;
}
else
{
result[i] = 0;
}
}
return result;
}
vi semiPrime = createSemiPrimes(200);
int main()
{
fastio;
int t = 0;
cin >> t;
while (t--)
{
int n = 0;
cin >> n;
if (n <= 6)
{
cout << "NO\n";
return 0;
}
bool possible = false;
for (int i = 6;i <= n;i++)
{
int diff = n - i;
if (semiPrime[diff] == 1 && semiPrime[i] == 1)
{
possible = true;
break;
}
}
if (possible) cout << "YES\n";
else cout << "NO\n";
}
return 0;
}
Thanks in advance 
