Codeforces B. T-primes

#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<map>
#include<bitset>

#define high 1000010

using namespace std;

typedef long long LL;
typedef vector<LL>vll;

bitset<high>bs;
LL prm[(high>>1)+9] , plen=0;
int len;
vll v;

void sieve()
{
    LL i,j;
    bs[0] = bs[1] = 0;
    bs.set();

    for(i=2; i<high; i++)
    {
        if(bs[i])
        {
            prm[plen++] = i;

            for(j=i*i; j<high; j+=i)
            {
                bs[j] = 0;
            }
        }
    }

    //for(i=0; i<100; i++) cout << prm[i] << " ";

    for(i=0; i<plen; i++)
    {
        v.push_back(prm[i] * prm[i]);
    }

    len = v.size();

    //for(i=0; i<100; i++) cout << v[i] << " ";
    //cout << len;
}
//void divisor(LL n)
//{
//    int i;
//
//    for(i=2; ; i++)
//    {
//        if(!(n % i))
//        {
//            cout << i << "\n";
//            break;
//        }
//    }
//}

int Search_Binary(LL itm)
{
    int lo=0, hi=len-1, mid;

    while(lo <= hi)
    {
        mid = (lo + hi) / 2;

        if(v[mid] == itm)
        {
            return mid;
        }

        else if(v[mid] > itm)
        {
            hi = mid - 1;
        }

        else if(v[mid] < itm)
        {
            lo = mid + 1;
        }
    }

    return lo;
}

int main()
{
    ios_base::sync_with_stdio(0);
    sieve();
    int n;
    while(cin >> n)
    {
        //divisor(n);
        int r;
        LL x;

        for(int i=0; i<n; i++)
        {
            cin >> x;
            r = Search_Binary(x);
            if(v[r] == x)
            {
                cout << "YES\n";
            }

            else
            {
                cout << "NO\n";
            }
        }
    }

    return 0;
}