题解 | #Factor Representation#

首先这题可以想到一种暴力枚举的方法，就是把每个$nn$从$22$~$\sqrt{n}\backslash sqrt\{n\}$枚举值因数，统计个数，但显然是要超时的（就算不超时，也很慢），所以我们要向优化一下。

首先，如果$nn$是个质数，那么肯定是输出No，所以可以特判一下。

//质数判定子程序
bool prime(int x) {
    if (x < 2) return false;//特判x<2的情况
    for (int i = 2; i <= sqrt(x); i ++)
        if (x % i == 0)
            return false;
    return true;
}

然后，既然是要有两个及以上的同样的质因数，所以我们可以直接用n % (i * i) == 0来判断，这样就少去了一个记录数组，同时减少了复杂度。

然后给出主程序代码：

while (cin >> n && n != 0) {
    bool flag = false;
    if(!prime(n)) {
        for (int i = 2; i <= sqrt(n); i ++)
            if (n % (i * i) == 0)//代码精华部分，需要思维
                flag = true;
    }
    if (flag) puts("Yes");//puts自动输出换行
    else puts("No");
}

Be will and be good!