题意描述
We know that prime numbers are positive integers that have exactly two distinct positive divisors. Similarly, we’ll call a positive integer t Т-prime, if t has exactly three distinct positive divisors.
You are given an array of n positive integers. For each of them determine whether it is Т-prime or not.
Input The first line contains a single positive integer, n (1 ≤ n ≤ 105), showing how many numbers are in the array. The next line contains n space-separated integers xi (1 ≤ xi ≤ 1012).
Please, do not use the %lld specifier to read or write 64-bit integers in С . It is advised to use the cin, cout streams or the %I64d specifier.
Output Print n lines: the i-th line should contain “YES” (without the quotes), if number xi is Т-prime, and “NO” (without the quotes), if it isn’t.
Examples input 3 4 5 6 output YES NO NO
题意
要想求只有三个因子的数，只需要判断这个数是否是素数的平方即可，可以先对所有的1~1e6的素数进行预处理，然后判断即可
AC代码
代码语言：javascript复制#include<bits/stdc .h>
#define x first
#define y second
#pragma GCC optimize(2)
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize(3)
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC target("avx","sse4","sse4.1","sse4.2","ssse3")
#pragma GCC target("f16c")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC diagnostic error "-std=c 14"
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef long long LL;
const int N=5005;
const int INF=0x3f3f3f3f;
const int MOD=998244353;
int a[N];
int dp[N];
bool check(int k){
if(k<2) return true;
for(int i=2;i*i<=k;i ){
if(k%i==0) return true;
}
return false;
}
int main(){
IOS;
set<LL> ans;
for(int i=2;i<=1000000;i ){
if(!check(i)){
ans.insert((LL)i*i);
}
}
int n;cin>>n;
while(n--){
LL x;cin>>x;
if(ans.count(x)) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
