507 Perfect Number

We define the Perfect Number is apositiveinteger that is equal to the sum of all itspositivedivisors 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 numbernwill not exceed 100,000,000. (1e8)

Complexity: O(sqrt(n))

The Idea: We iterate through every possible number that can factor to n and sum up the results. There are a few optimizations here. First, a factor will not exceed sqrt(n), since sqrt(n)*sqrt(n) == n.

Input:
 28

Sum:
 1

Explanation:
 28 = 1    +    2    +    4    +    7    +    14
      start
                ^------------------------------^
                          ^---------^
class Solution(object):
    def checkPerfectNumber(self, num):
        """
        :type num: int
        :rtype: bool
        """
        if num == 1:
           return False

        acc_sum = 1
        max_fact = int(math.sqrt(abs(num)))
        for i in range(2, max_fact + 1):
            if num % i == 0:
                acc_sum += i + num / i

        return acc_sum == num

Last updated