跳至主要內容

507. 完美数


507. 完美数

🟢   🔖  数学  🔗 力扣open in new window LeetCodeopen in new window

题目

A perfect numberopen in new window 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 推出。
    • inum / 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自除数[✓]数学🟢🀄️open in new window 🔗open in new window