#CF230B. T 质数

T 质数

CF230B T-primes

题目描述

\hspace{15pt}我们知道,质数是只有两个不同的正因数的正整数。类似地,我们称一个正整数 tt 为 T 质数,如果 tt 恰好有三个不同的正因数。

\hspace{15pt}给定一个含有 nn 个正整数的数组 x1,x2,…,xnx_1,x_2,\dots,x_n,你需要判断其中每个数是否是 T 质数。

输入格式

\hspace{15pt}第一行输入一个整数 n(1≦n≦105)n \left(1 \leqq n \leqq 10^5 \right),代表数组中的元素个数。

\hspace{15pt}第二行输入 nn 个整数 $x_1,x_2,\dots,x_n \left(1 \leqq x_i \leqq 10^{12} \right)$,代表数组中的元素。

输出格式

\hspace{15pt}输出 nn 行,第 ii 行输出一个字符串:如果 xix_i 是 T 质数,输出 "YES"\texttt{"YES"};否则输出 "NO"\texttt{"NO"}。

测试样例

3
4 5 6

YES
NO
NO

样例 1 解释

\hspace{15pt}样例中共有三个数。第一个数 44 恰好有三个因数 1,2,41,2,4,因此对这个数输出 "YES"\texttt{"YES"};第二个数 55 有两个因数 1,51,5,第三个数 66 有四个因数 1,2,3,61,2,3,6,因此这两个数的答案都是 "NO"\texttt{"NO"}。

数据范围与提示

\hspace{15pt}请注意:xix_i 可达 101210^{12},超出了 3232 位整数的范围,请使用 6464 位整数(C++ 中的 long long)存储并在读写时使用 %lld 或 cin/cout。