题解

史诗级猎奇做法。

观察样例，发现和答案和素性强相关。

首先打了一个素数筛，没筛 $1$ 因为 $A=\{1\}$ 显然是合法的。

然后交上去 WA 了 3 个点。

再次观察样例，发现 $4$ 没被写进去。

所以我们推测 $4$ 很重要。

前往 OEIS，输入 $2,3,4,5,7,11$，发现了这条结果。

然后这题就被我水过了。

#include <iostream>
#include <cstdio>
using namespace std;
bool vis[1000005];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	for(int i = 2; i <= 1000; i++){
		if(vis[i]) continue;
		for(int j = i * 2; j <= 1000000; j += i){
			vis[j] = 1;
		} 
	}
	vis[1] = vis[4] = 0;
	int t;
	cin >> t;
	while(t--){
		int n;
		cin >> n;
		cout << (vis[n] ? "NO\n" : "YES\n");
	}

	return 0;
}