507. 完美数

1. 题目描述

https://leetcode.cn/problems/perfect-number/

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

给定一个 整数 n， 如果是完美数，返回 true；否则返回 false。

示例：
输入：num = 28
输出：true
解释：28 = 1 + 2 + 4 + 7 + 14
1, 2, 4, 7, 和 14 是 28 的所有正因子。

2. 解题思路

通过枚举法找到整数n的所有正因子，首先想到从1枚举到n/2，提交后发现超时了，说明枚举的还是太多。因为整数的正因子除了1和自身外都是成对出现，比如28的正因子中有（2，14）和（4，7），加上之前做过类似的使用枚举法来解的题，所以很自然能想到枚举到$\sqrt{n}$，只需要找到每对因子中小的一个，相当于找到了一对。

• python3

class Solution:
    def checkPerfectNumber(self, num: int) -> bool:
        if num == 1:
            return False
        sum = 1
        d = 2
        while d * d <= num:
            if num % d == 0:
                sum += d  # 一对正因子中小的那个, 一对因子相同时只加上一个
                if d * d < num:
                    sum += num / d  # 一对正因子中大的那个
            d += 1
        return num == sum

• C++

class Solution {
    
public:
    bool checkPerfectNumber(int num) {
    
        int sum = 1;
        int d = 2;
        if (num == 1) return false;
        while (d * d <= num){
    
            if (num % d == 0){
    
                sum += d;
                if (d*d < num) sum += num / d;
            }
            d += 1; 
        }
        return sum == num;
    }
};