CodeForces 230B

#include 
#include 
#include 
using namespace std;

// eratosthenes 埃式素数筛
// 可被三个除数整除的数<=>素数的平方，其三个除数为(1,n,prims)
void findPrims(set& tprims, vector& flags)
{
    flags[0] = flags[1] = false;
    for (long long i = 2; i < flags.size(); i++)
    {
        if (flags[i])
        {
            tprims.insert(i*i); // 素数平方即是T-Prims
            for (long long j = 2*i; j < flags.size(); j += i)
            {
                flags[j] = false; // 素数的倍数不是素数
            }
        }
    }
}

int main()
{
    int n;
    long long target;
    set tprims;
    vector flags(1000001, true);
    findPrims(tprims, flags);
    while(cin >> n)
    {
        while (n--)
        {
            cin >> target;
            if(tprims.find(target) != tprims.end()) 
                cout << "YES" << endl;
            else 
                cout << "NO" << endl;
        }
    }
}