首先这题可以想到一种暴力枚举的方法,就是把每个从~枚举值因数,统计个数,但显然是要超时的(就算不超时,也很慢),所以我们要向优化一下。
首先,如果是个质数,那么肯定是输出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!