题解（更新了

这道题就相比之前那对好数简单的多
首先我们试试正常方法：一个一个遍历，看看是否有三个因子

bool check(long long x){
    int ct = 0;
    long long i;
    for(i = 1; i <= x; i++){
        ct += (x % i == 0); //直接加布尔值，不用if判断
    return ct == 3; //判断是否正好有三个因子

时间复杂度：$O(x)$
但是代入$x <= 10^{12}$会发现百分百超时
name，还有其他办法吗？
我们注意到，一个数的因子，一定有1和它本身，也就是两个因子（1除外）
于是我们只要找到剩下那个因子就行了
但我们又又又又注意到，如果一个数x有因子y，那它就必然有因子(x/y)，那在算上1和x就有四个因子了呀！
没错，可是如果y和(x/y)是一样的数呢？
没错，那个数就是完全平方数！
而且它的平方根必须是质数，否则就会有5个因子，7个因子，甚至更多
于是，我们再判断一下质数就可以了

#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
int a[100005];
int sqrt(int x){//二分求平方根，时间复杂度O(logx)
	int left = 1, right = 1e6;
	while(left <= right){
		int mid = (left + right) / 2;
		if(mid * mid == x) return mid;
		if(mid * mid < x) left = mid + 1;
		else right = mid - 1;
	}return -1;
}
bool check(int x){
	int sqrtx = sqrt(x);
	if(sqrtx == -1) return 0;//如果不是完全平方数，那就至少有4个因子
	if(sqrtx < 2) return 0; //小于二也不是质数
	for(int i = 2; i * i <= sqrtx; i++){//判断质数，一眼看出来O(sqrt(sqrt(x)))
		if(sqrtx % i == 0) return 0;//如果不是质数，那就至少包含5个因子
	}return 1;//否则就有3个因子
}
signed main(){
	int t, x;
	scanf("%lld", &t);
	while(t--){
		scanf("%lld", &x);
		printf(check(x) ? "YES\n" : "NO\n");
	}

	return 0;
}

单个时间复杂度：$O(\sqrt{\sqrt{x}})$
当然，我们可以预先筛一遍，然后用O(logn)的时间复杂度去判断

#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
bool vis[1000005];
void _init(){//埃式筛模版O(nloglogn)
	const int n = 1e6;//sqrt(x)最大不超过1e6
	vis[0] = vis[1] = 1;
	for(int i = 1; i * i <= n; i++){
		if(!vis[i]){
			for(int j = i * 2; j <= n; j += i){
				ct++;
				vis[j] = 1;
			}
		}
	}
}
int sqrt(int x){//时间复杂度O(logx)
	int left = 1, right = 1e6;
	while(left <= right){
		int mid = (left + right) / 2;
		if(mid * mid == x) return mid;
		if(mid * mid < x) left = mid + 1;
		else right = mid - 1;
	}return -1;
}
bool check(int x){
	int sqrtx = sqrt(x);
	if(sqrtx == -1) return 0;
	return !vis[sqrtx];//这样判断质数时间复杂度就降为O(1)了
}
signed main(){
	_init();
	int t, x;
	scanf("%lld", &t);
	while(t--){
		scanf("%lld", &x);
		printf(check(x) ? "YES\n" : "NO\n");
	}

	return 0;
}

单个数时间复杂度：$O(logx)$
整体时间复杂度：$O(2200000 + tlogx)$（大常数就不省了）