507. 完美数

🟢   🔖  数学  🔗 力扣 LeetCode

题目

A perfect number is a positive integer that is equal to the sum of its positive divisors , excluding the number itself. A divisor of an integer x is an integer that can divide x evenly.

Given an integer n, return true ifn is a perfect number, otherwise returnfalse.

Example 1:

Input: num = 28

Output: true

Explanation: 28 = 1 + 2 + 4 + 7 + 14

1, 2, 4, 7, and 14 are all divisors of 28.

Example 2:

Input: num = 7

Output: false

Constraints:

• 1 <= num <= 10^8

题目大意

对于一个 正整数 ，如果它和除了它自身以外的所有 正因子 之和相等，我们称它为 「完美数」 。

给定一个 **整数 **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 <= 10^8

解题思路

对于一个数 num，可以从 1 开始枚举其所有可能的正因子，累加这些因子的和，如果 sum == num，则 num 是完美数。

1. 如果 num <= 1，直接返回 false，因为完美数定义中要求「正因子之和不包括自身」。
2. 初始化累加因子的和 sum = 1，因为 1 是任何数的正因子。
3. 枚举所有可能的因子：
   • 如果一个数可以被 i 整除，则 num / i 也是一个因子。
   • 因此，遍历时只需从 2 遍历到 sqrt(num)，因为超出 sqrt(num) 的部分可以通过 num / i 推出。
   • 将 i 和 num / i 加入累加因子和 sum 中，注意要避免重复累加平方根的因子。
     • 例如，49 的平方根是 7，7 * 7 = 49，因子 7 只计算一次。
4. 遍历结束后，将正因子之和与 num 比较。如果相等，返回 true；否则返回 false。

复杂度分析

• 时间复杂度：O(sqrt(num))，遍历范围是从 2 到 sqrt(num)。
• 空间复杂度：O(1)，只使用了固定数量的变量存储中间结果。

代码

/**
 * @param (number} num
 * @return {boolean}
 */
var checkPerfectNumber = function (num) {
	if (num <= 1) return false; // 边界情况，1 不是完美数

	let sum = 1; // 因为 1 是任何数的正因子
	for (let i = 2; i * i <= num; i++) {
		if (num % i === 0) {
			sum += i; // 累加较小的因子
			if (i !== num / i) {
				sum += num / i; // 累加较大的因子
			}
		}
	}
	// 比较累加因子和 sum 与 num
	return sum === num;
};

相关题目

题号	标题	题解	标签	难度	力扣
728	自除数	[✓]	数学	🟢	🀄️ 🔗