0507._Perfect_Number.md

507. Perfect Number

难度: Easy

刷题内容

原题连接

• https://leetcode.com/problems/perfect-number/description/

内容描述

We define the Perfect Number is a positive integer that is equal to the sum of all its positive divisors except itself.

Now, given an integer n, write a function that returns true when it is a perfect number and false when it is not.
Example:
Input: 28
Output: True
Explanation: 28 = 1 + 2 + 4 + 7 + 14
Note: The input number n will not exceed 100,000,000. (1e8)

解题方案

思路 1 - 时间复杂度: O(lgN)- 空间复杂度: O(1)******

用了一个比较巧妙的方法，首先排除一些 corner case，num 小于等于1的时候直接返回 False

然后后面开始这个方法，就是我们其实不需要对所有小于 num 的数字做遍历，只需要从 2 遍历到 int(sqrt(num)) 即可， 然后每次可以整除的时候都加上当前数字 i 和 num//i，然后初始化的时候让 sums = 1 ，这样最后就是不包含自己的所有因子的和，最后 return sum == num

beats 95.73%

from math import sqrt
class Solution(object):
    def checkPerfectNumber(self, num):
        """
        :type num: int
        :rtype: bool
        """
        if num <= 1:
            return False
        sums = 1
        for i in range(2, int(sqrt(num))+1):
            if num % i == 0:
                sums += i + num // i
        return sums == num