Easy

题目描述

完美数是一个正整数，等于它的所有正因数的和（不包括它自己）。一个整数 x 的因数是能够整除 x 的整数。

给定一个整数 n，如果 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

解题思路

这道题有两种解法：

方法一：数学优化解法（推荐）

完美数非常稀有，在题目给定的范围内（1 到 10^8）只有5个完美数：6, 28, 496, 8128, 33550336。我们可以直接判断输入是否为这些数之一。

方法二：因数枚举解法

暴力枚举所有因数并求和。关键优化是只需要遍历到 √num，因为因数总是成对出现的。对于每个因数 i，它的配对因数是 num/i。需要注意避免重复计算（当 i = √num 时）。

时间复杂度方面，数学解法为 O(1)，因数枚举为 O(√n)。考虑到完美数的稀有性和题目约束，数学解法是最优选择。

代码实现中，我们采用数学解法，直接判断是否为已知的完美数。

代码实现

class Solution {
public:
    bool checkPerfectNumber(int num) {
        return num == 6 || num == 28 || num == 496 || num == 8128 || num == 33550336;
    }
};

class Solution:
    def checkPerfectNumber(self, num: int) -> bool:
        return num in {6, 28, 496, 8128, 33550336}

public class Solution {
    public bool CheckPerfectNumber(int num) {
        return num == 6 || num == 28 || num == 496 || num == 8128 || num == 33550336;
    }
}

/**
 * @param {number} num
 * @return {boolean}
 */
var checkPerfectNumber = function(num) {
    if (num <= 1) return false;
    
    let sum = 1;
    for (let i = 2; i * i <= num; i++) {
        if (num % i === 0) {
            sum += i;
            if (i * i !== num) {
                sum += num / i;
            }
        }
    }
    
    return sum === num;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度数学解法因数枚举解法
时间复杂度O(1)O(√n)
空间复杂度O(1)O(1)

相关题目