1952 三除数

方法一：暴力枚举

由于此题的数据量为 1e4，可以考虑统计 1 ~ n 以内所有 n 的正除数，最后判断即可；

Python版本

C++版本

复杂度分析

• 时间复杂度：O(N)。

• 空间复杂度：O(1)。

方法二：枚举 + 质因数判断

对于除了1以外的任意正整数而言，它至少有自身和1两个正除数，此外，对于一个数开平方根，增多一个因数，但此因数必须是质数，否则还可以再拆分因数；

枚举 2 ~ sqrt(n) 的所有数字，判断其是否为平方根且为质数即可；

Python版本

C++版本

复杂度分析

• 时间复杂度：。

• 空间复杂度: O(1)。

方法三：枚举 + 贡献度累加

任意一个正整数，如果能作为 n 的一个除数，n 与这个除数的商也是一个除数。因此我们只需要枚举 1 ~ sqrt(n)以内的数字即可。如果能被n整除且是平方根，则除数和商相同，贡献度为1，不是平方根则说明同时选中了它以及将它作为除数得到的商，贡献度为2；最后判断计数器的值是否为3即可；

Python版本

C++版本

复杂度分析

• 时间复杂度：O(logn)。

• 空间复杂度：O(1)。

备注

1. 方法二实际上是验证 n 是否存在一个质数的平方根，如果有，则说明至少有三个整除数。这种假设构建在这个数已经有两个除数的情况下，因此可以从2开始遍历；

2. 方法三计算贡献度时，需要分别验证能够整除n的除式中，较大数，较小数，以及是否存在平方根，本质上还是统计正除数的个数，因此要从1开始遍历；如果从2开始，那么就少统计了1作为任意大于1的数字的整除数的情况；