三质数c+ +（XJOI的编程题）

Question

三质数提交(Submit)
中文

时间限制：1s 空间：256M
题目描述：
一个数的约数也称为因子，比如1是6的因子，2是6的因子，6是6的因子。

质数只有两个因子，1和它本身

现在定义一种新的质数，三质数，三质数只有三个不同的因子。比如4是三质数，因为它有1,2,4三个因子。比如6不是三质数，因为6有1,2,3,6四个因子。现在有一些数，你需要判断他们是不是三质数。

输入格式：
第一行一个整数T，表示有T组测试数据。

每组测试数据输入一个整数n
输出格式：
对于每组测试数据，判断是否是三质数，如果是输出YES，否则输出NO

样例输入：
3
4
5
6
样例输出：
YES
NO
NO
约定：
1<=n<=1012,数据组数不超过103

Answer 1

三质数只可能是平方数（因为因数都是成对出现的，除非两个因数相等，不然不可能出现奇数个因数的情况。除去1和它本身，剩下来的一个因数x也必定是质数，不然它可以继续做质因数分解， 那么会产生更多的因数），假设要判断的数是n，你别用i从1到n去判断n的因数个数。 直接用i从1到int(sqrt(n)), 同时要让i取这个范围内的质数， 判断i^2==n，如果是true,那么n就是三素数