这道题就相比之前那对好数简单的多 首先我们试试正常方法：一个一个遍历，看看是否有三个因子 时间复杂度：O(x)O(x)O(x) 但是代入x<=1012x <= 10^{12}x<=1012会发现百分百超时 name，还有其他办法吗？ 我们注意到，一个数的因子，一定有1和它本身，也就是两个因子（1除外） 于是我们只要找到剩下那个因子就行了 但我们又又又又注意到，如果一个数x有因子y，那它就必然有因子(x/y)，那在算上1和x就有四个因子了呀！ 没错，可是如果y和(x/y)是一样的数呢？ 没错，那个数就是完全平方数！ 而且它的平方根必须是质数，否则就会有5个因子，7个因子，甚至更多 于是，我们再判断一下质数就可以了 单个时间复杂度：O(x)O(\sqrt{\sqrt{x}})O(x ) 当然，我们可以预先筛一遍，然后用O(logn)的时间复杂度去判断 单个数时间复杂度：O(logx)O(logx)O(logx) 整体时间复杂度：O(2200000+tlogx)O(2200000 + tlogx)O(2200000+tlogx)（大常数就不省了）

题目解析 我们可以先列举几个好数的数，4 9 25 49。 可以发现对于任意一个 aia_iai 来说，如果它是一个完全平方数，并且 ai\sqrt{a_i}ai 为一个质数，则它是好数。所以可以先用埃氏筛筛出所有 ≤maxai\leq \sqrt{max_{a_i}}≤maxai 的质数，因为只有这一半是会被用到的，最后判断这个数是不是为完全平方数即可。 AC代码 复杂度 埃氏筛的复杂度为：O(nlog⁡log⁡n)O(n\log\log n)O(nloglogn)

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

三个因子肯定是平方数 但是要排除一种可能 这种因子是合数，有其他因数 所以他的平方也就也有其他因数 所以必须是质因子 上代码