题解

第四题：

读题：

问哪些数含有三个因子

---

思路：

想到快捷思路稍微有点难，因为乘积二分即开根号 O(log2(n)) 找因数亲自试验会超时的
这道题考察数学的完全平方数和素数（质数）
我们都知道，一般而言因数是成双成对出现的，但是完全平方数只有奇数个因数，因为sqrt(sqr(n))=sqr(n)/sqrt(sqr(n))，那么我们只要确保n是一个素数就可以使sqr(n)拥有三个因数，分别是1、n和sqr(n)这三个

---

代码：

#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;
bool prime(ll n){
    for(int i=2;i*i<=n;i++)if(!(n%i))return 0;
    return 1;
}
int main(){
    int n;
    cin>>n;
    while(n--){
        ll t;
        cin>>t;
        if(t==1)cout<<"NO\n";
        else{
            double p1=sqrt(t);
            int p2=p1;
            bool f=p1==p2?prime(p2):0;
            if(f)cout<<"YES\n";
            else cout<<"NO\n";
        }
    }return 0;
}