Codeforces Round 142 (Div. 2) B

Codeforces Round 142 (Div. 2) B.cpp

//By Brickgao
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;

bool is[1000020];
__int64 prm[500000];

__int64 getprm(__int64 n)
{
    __int64 i, j, k = 0;
    __int64 s, e = (__int64)(sqrt(0.0 + n) + 1);
    memset(is, true, sizeof(is));
    prm[k++] = 2;
    is[0] = is[1] = false;
    for (i = 4; i < n; i += 2)
        is[i] = false;
    for (i = 3; i < e; i += 2)
    if (is[i])
    {
        prm[k++] = i;
        for (s = i * 2, j = i * i; j < n; j += s)
            is[j] = false;
    }
    for ( ; i < n; i += 2)
        if (is[i])
            prm[k++] = i;
    return k;
}

int main()
{
    __int64 n, x, tmp1, tmp2, k;
    k = getprm(1000010);
    cin >> n;
    for(__int64 i = 1; i <= n; i++)
    {
        cin >> x;
        tmp1 = sqrt(x);
        tmp2 = tmp1 * tmp1;
        if(tmp2 == x && is[tmp1])
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}