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.
- The input number n will not exceed 100,000,000. (1e8)
Example:
- Input: 28
- Output: True
- Explanation: 28 = 1 + 2 + 4 + 7 + 14
Python Solution 1:
class Solution(object):
def checkPerfectNumber(self, num):
"""
:type num: int
:rtype: bool
"""
if num == 1: return False
l, r = 2, num // 2
_num = num
_num -= 1
while l < r:
tmp = num // l
if l * tmp == num:
_num -= l
_num -= tmp
l += 1
r = tmp - 1
else:
l += 1
r = tmp
if l == r and l * r == num:
_num -= l
return _num == 0
Python Solution 2:
class Solution(object):
def checkPerfectNumber(self, num):
"""
:type num: int
:rtype: bool
"""
if num == 1: return False
l, r = 2, num // 2
sum = 1
while l < r:
if num % l == 0:
sum += l + r;
l += 1
r = num // l;
if l == r and l * r == num:
sum += l
return sum == num
Summary:
- A good method for problem about diviors.
LeetCode: 507. Perfect Number
近期评论