#danglam228

#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 1e7;
int prime[N + 1];
void sang(long long res) {
    for (long long i = 0; i <= res; ++i) {
        prime[i] = 1;
    }
    prime[0] = prime[1] = 0;
    for (long long i = 2; i * i <= res; ++i) {
        if (prime[i]) {
            for (long long j = i * i; j <= res; j += i) {
                prime[j] = 0;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    freopen("TNUM.INP","r",stdin);
    freopen("TNUM.OUT","w",stdout);
    cin >> n;
    long long a[n];
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    long long d1 = 0;
    for (int i = 0; i < n; ++i) {
        d1 = max(d1, a[i]);
    }
    
    long long d = sqrt(d1);
    sang(d);

    for (int i = 0; i < n; ++i) {
        long long num = a[i];
        long long sq = sqrt(num);
        if (num <= 1) {
            cout << "NO" << endl;
        } else if (sq * sq == num && prime[sq]) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

Số chính phương thì ước là lẻ CHỨ không phải số chính phương thì luôn có 3 ước. Ví dụ: số 36: Có các ước là 1,2,3,6,12,18,36. Do đó, bạn kiểm tra xem số đó có phải số chính phương không, sau đó dùng thuật toán O(sqrt(N)) để đếm số ước