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 modified 4yr ago