We know that prime numbers are positive integers that have exactly two distinct positive divisors. Similarly, we'll call a positive integer *t* Т-prime, if *t* has exactly three distinct positive divisors.

You are given an array of *n* positive integers. For each of them determine whether it is Т-prime or not.
The first line contains a single positive integer, *n* (1 ≤ *n* ≤ 10<sup class="upper-index">5</sup>), showing how many numbers are in the array. The next line contains *n* space-separated integers *x*<sub class="lower-index">*i*</sub> (1 ≤ *x*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">12</sup>).

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is advised to use the cin, cout streams or the %I64d specifier.
#include <bits/stdc++.h>

using namespace std;

#define num int64_t

#define MAX_NUM 1000001
array<bool, MAX_NUM> sieves;

void sieve(){
    sieves.fill(true);
    num i = 2;
    sieves[2] = true;
    while(pow(i, 2) <= MAX_NUM){
      
        if(sieves[i]){
            num j = i * 2;
            while(j <= MAX_NUM){
                sieves[j] = false;
                j += i;
            }
        }
        ++i;
    }
}
int32_t main(){
    sieve();
    num N;
    cin >> N;
    cin.tie(0);
   // ios::sync_with_stdio(false);

    vector<num> nums(N);
    for(num i = 0;i< N;i++){
        cin >> nums[i];
    }
    for(auto n: nums){
        auto x = sqrt(n);
        auto index = int(floor(x));
       // cout << "index of " << x << " is " << index << " and the value is " << sieves[index]<< '\n';

        if(ceil(x) == floor(x) && sieves[ index]){
            cout << "YES\n";
        }
        else{
            cout << "NO\n";
        }
    }


}