完美数
难度:
标签:
题目描述
对于一个 正整数，如果它和除了它自身以外的所有 正因子 之和相等，我们称它为 「完美数」。
给定一个 整数 n， 如果是完美数，返回 true；否则返回 false。
示例 1：
输入：num = 28 输出：true 解释：28 = 1 + 2 + 4 + 7 + 14 1, 2, 4, 7, 和 14 是 28 的所有正因子。
示例 2：
输入：num = 7 输出：false
提示：
1 <= num <= 108
代码结果
运行时间: 24 ms, 内存: 16.6 MB
/*
* 思路：
* 使用 Java 8 的流（Stream）API 来简化因子的求和。
* 我们可以利用 IntStream 来生成从 1 到 num/2 的范围，并筛选出所有的因子，最后求和。
*/
import java.util.stream.IntStream;
public class PerfectNumberStream {
public boolean checkPerfectNumber(int num) {
if (num <= 1) return false; // 1 不是完美数
int sum = IntStream.rangeClosed(1, num / 2)
.filter(i -> num % i == 0)
.sum();
return sum == num;
}
}解释
方法:
此题解的核心思想是利用数学方法减少不必要的迭代。对于一个给定的正整数num，如果它是一个完美数，那么它所有的正因子之和（除了它自身）应该等于num。题解中首先排除了1，因为1没有除了自身以外的正因子。接着，从2开始遍历到sqrt(num)，寻找所有可能的因子。如果d是num的因子，则num/d也是num的因子。这样可以在O(sqrt(n))的时间复杂度内找到所有的因子。对于每个找到的因子d，如果d*d不等于num，那么可以将num/d也加入到因子之和中。最后，比较计算出的因子之和与num是否相等，从而判断是否为完美数。
时间复杂度:
O(sqrt(n))
空间复杂度:
O(1)
代码细节讲解
🦆
为什么题解中提到'从2开始遍历到sqrt(num)'，而不是直接遍历到num？这样做的数学原理是什么？
▷🦆
在算法中，如果`d * d == num`，为什么不需要将num/d加入因子之和？这样做的原因是什么？
▷🦆
题解中提到的时间复杂度是O(sqrt(n))，这个复杂度是如何计算得出的？
▷相关问题
自除数
自除数 是指可以被它包含的每一位数整除的数。
- 例如，
128是一个 自除数 ，因为128 % 1 == 0，128 % 2 == 0，128 % 8 == 0。
自除数 不允许包含 0 。
给定两个整数 left 和 right ，返回一个列表，列表的元素是范围 [left, right] 内所有的 自除数 。
示例 1：
输入：left = 1, right = 22 输出：[1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]
示例 2:
输入：left = 47, right = 85 输出：[48,55,66,77]
提示：
1 <= left <= right <= 104