Subtask 1: ~n, a_i \le 10^4~

Duyệt từng số, với mỗi số duyệt để đếm ước.

Độ phức tạp: ~O~ (~n \times \sqrt a_i~) hoặc ~O~ (~n \times a_i~) tùy cách cài đặt.

Subtask 2: ~a_i \le 10^{10}~

Nhận xét quan trọng: Số có đúng 3 ước là bình phương của một số nguyên tố.

Thật vậy, xét phân tích thừa số nguyên tố ~n = p_1^{q_1} \times p_2^{q_2} \times ... \times p_k^{q_k}~, để ~n~ có 3 ước ta cần ~(q_1 + 1) \times (q_2 + 1) \times ... \times (q_k + 1) = 3~. Lúc này, khả năng duy nhất là ~k = 1~ và ~q_1 = 2~, hay ~n~ là bình phương một số nguyên tố.

Lúc này, ta kiểm tra số chính phương và kiểm tra số nguyên tố là được.

Độ phức tạp: ~O~ (~n \times \sqrt {\sqrt a_i}~).

Subtask 3: ~a_i \le 10^{12}~

Sử dụng sàng nguyên tố để kiểm tra số nguyên tố.

Độ phức tạp: ~O~ (~n \times log~ ~n~).

Code mẫu:

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pp pair <int, int>
#define fi first
#define se second
#define yes cout << "YES\n"
#define no cout << "NO\n"

const int N = 1e6 + 9;
const int INF = 1e18 + 9;

int n, a[N];
int cnt[N];

bool notPrime[N];

void sieve (){
    notPrime[0] = notPrime[1] = 1;
    for (int i = 2; i * i < N; i++) if (notPrime[i] == 0){
        for (int j = i * i; j < N; j += i) notPrime[j] = 1;
    }
}

signed main (){
    ios_base::sync_with_stdio (false);
    cin.tie (NULL);
    cout.tie (NULL);
    int res = 0;
    cin >> n;
    for (int i = 1; i <= n; i++){
        int x; cin >> x;
        int y = sqrt (x);
        if (y * y != x){
            no; continue;
        }
        if (notPrime[y]){
            no; continue;
        }
        yes;
    }
}