简要题意：
判断一个数是否只有 (3) 个因数。
首先，如果一个数有奇数个因数，那么这个数是完全平方数。
道理很简单：因数是成对的，那么必然存在 (k^2 = n)，此时 (k) 就是单个的，(n) 就是完全平方数。
但是，你会发现，并不是所有的完全平方数都一定有三个因数。
比方说： (36).
(1 space 2 space 3 space 4 space6 space 9 space 12 space 18 space 36)
一看这么多因数就不是3个
显然，我们发现：
若 (n = k ^ 2)，用 (f_n) 表示 (n) 的因数个数，则：
[f_n = 2 imes f_k-1
]
原因也很简单：因数是成对出现的，减去重复的 (k) 一个。
那么，此时；
[2 imes f_k - 1 = 3
]
[f_k = 2
]
也就是 (f_k) 是质数！
我们发现， (n leq 10^{12})，则 (k leq sqrt{n} leq 10^6).
显然，我们可以欧拉筛出 (leq 10^6) 的质数表，然后 (O(1)) 判断。
综上：
(n) 不是完全平方数，或者 (sqrt{n}) 不是质数时，答案为 ( exttt{NO}).
否则答案为 ( exttt{YES}).
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+1;
inline ll read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
ll x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
bool h[N];
int prime[N],f=0;
inline void Euler() {
h[1]=1;
for(int i=2;i<N;i++) {
if(!h[i]) prime[++f]=i;
for(int j=1;j<=f && i*prime[j]<N;j++) {
h[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
} //欧拉筛模板
int main(){
int T=read(); Euler(); while(T--) {
ll n=read();
if(n==1) puts("NO");
else {
ll q=sqrt(n);
if(q*q-n || h[q]) puts("NO");
else puts("YES");
}
}
return 0;
}
洛谷上竟然标蓝题，我谔谔